×

Time-parallel solutions to differential equations via functional optimization. (English) Zbl 1415.65154

Summary: We describe an approach to solving a generic time-dependent differential equation (DE) that recasts the problem as a functional optimization one. The techniques employed to solve for the functional minimum, which we relate to the Sobolev Gradient method, allow for large-scale parallelization in time, and therefore potential faster “wall-clock” time computing on machines with significant parallel computing capacity. We are able to come up with numerous different discretizations and approximations for our optimization-derived equations, each of which either puts an existing approach, the Parareal method, in an optimization context, or provides a new time-parallel (TP) scheme with potentially faster convergence to the DE solution. We describe how the approach is particularly effective for solving multiscale DEs and present TP schemes that incorporate two different solution scales. Sample results are provided for three differential equations, solved with TP schemes, and we discuss how the choice of TP scheme can have an orders of magnitude effect on the accuracy or convergence rate.

MSC:

65L05 Numerical methods for initial value problems involving ordinary differential equations
65Y05 Parallel numerical computation
Full Text: DOI

References:

[1] Amodio, P; Brugnano, L, Parallel solution in time of ODEs: some achievements and perspectives, Appl Numer Math, 59, 424-435, (2009) · Zbl 1166.65349 · doi:10.1016/j.apnum.2008.03.024
[2] Conte SD, deBoor C (1972) Elementary numerical analysis. McGraw-Hill, New York · Zbl 0257.65002
[3] Engblom, S, Parallel in time simulation of multiscale stochastic chemical kinetics, Multiscale Model Sim, 8, 46-68, (2009) · Zbl 1184.92064 · doi:10.1137/080733723
[4] Engquist, W, The heterogeneous multi scale methods, Commun Math Sci, 1, 87-132, (2003) · Zbl 1093.35012 · doi:10.4310/CMS.2003.v1.n1.a8
[5] Farhat C, Cortial J (2008) A time-parallel implicit method for accelerating the solution of nonlinear structural dynamics problems. Int J Num Methods Eng 1-25 · Zbl 1155.74428
[6] Fox C (1987) An introduction to the calculus of variations. Courier Dover Pub · Zbl 0653.49001
[7] Frantziskonis, G; Muralidharan, K; Deymier, P; Simunovic, S; Nukala, P; Pannala, S, Time-parallel multiscale/multiphysics framework, J Comput Phys, 228, 8085-8092, (2009) · Zbl 1175.65080 · doi:10.1016/j.jcp.2009.07.035
[8] Gear, CW, Parallel methods for ordinary differential equations, Calcolo, 25, 1-20, (1987) · Zbl 0675.65068
[9] Gear, CW; Kevrekidis, IG, Projective methods for stiff differential equations: problems with gaps in their eigenvalue spectrum, SIAM J Sci Comp, 24, 109-1110, (2003) · Zbl 1034.65056 · doi:10.1137/S1064827501388157
[10] Harden C, Peterson J (2006) Combining the parareal algorithm and reduced order modeling for time dependent partial differential equations. (Harden, C. and Peterson, J. on-line post) · Zbl 1154.65061
[11] Iserles A (1996) A first course in the numerical analysis of differential equations, 2nd edn. Cambridge University Press, Cambridge · Zbl 0841.65001
[12] Lederman C, Joshi A, Dinov I, Vese L, Toga A, Van Horn JD (2011b) The generation of tetrahedral mesh models for neuroanatomical MRI 55:153-164 · Zbl 0984.65085
[13] Lederman C, Vese L, Chien A (2011a) Registration for 3D morphological comparison of brain aneurysm growth. Adv Visual Comput 6938:392-399 · Zbl 1220.65166
[14] Lin T, Dinov I, Toga A, Vese L (2010) Nonlinear elasticity registration and sobolev gradients. Biomed Image Regist 6204:269-280
[15] Lions, J-L; Maday, Y; Turinici, G, A parareal in time discretization of pde’s, CR Acad Sci Paris Serie I, 332, 661-668, (2001) · Zbl 0984.65085 · doi:10.1016/S0764-4442(00)01793-6
[16] Mahavier WT (2011b) Solving boundary value problems numerically using steepest descent in Sobolev spaces. Missouri J Math Sci 11:19-32 · Zbl 1097.65535
[17] Majid, A; Sial, S, Approximate solutions to Poisson-Boltzmann systems with Sobolev gradients, J Comput Phys, 230, 5732-5738, (2011) · Zbl 1220.65166 · doi:10.1016/j.jcp.2011.03.056
[18] Martin, G, A waveform relaxation algorithm with overlapping splitting for reaction diffusion equations, Numer Linear Algebra Appl, 1, 1-7, (1993)
[19] Mujeeb, D; Neuberger, JW; Sial, S, Recursive form of Sobolev gradient method for ODEs on long intervals, Int J Comput Math, 85, 1727-1740, (2008) · Zbl 1154.65061 · doi:10.1080/00207160701558465
[20] Neuberger J (1997) Sobolev gradients and differential equations. Lecture Notes in Mathematics 1670. Springer · Zbl 0935.35002
[21] Renka, RJ, Constructing fair curves and surfaces with a Sobolev gradient method, Comput Aided Geom Des, 21, 137-149, (2004) · Zbl 1069.65565 · doi:10.1016/j.cagd.2003.07.006
[22] Renka, RJ, Image segmentation with a Sobolev gradient method, Nonlinear Anal, 71, 774-780, (2009) · Zbl 1238.94009 · doi:10.1016/j.na.2008.11.070
[23] Samaddar, D; Newman, DE; Sanchez, R, Parallelization in time of numerical simulations of fully-developed plasma turbulence using the parareal algorithm, J Comput Phys, 229, 6558, (2010) · Zbl 1425.76090 · doi:10.1016/j.jcp.2010.05.012
[24] Sand J, Burrage K (1998) A Jacobi waveform relaxation method for ODEs. SIAM J Sci Comput 20(2):534-552. ISSN 1064-8275 · Zbl 0923.65045
[25] Stone HS (1975) Parallel tridiagonal equation solvers. ACM Trans Math Softw l(4):289-307 · Zbl 0315.65018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.