The parareal in time algorithm allows for efficient parallel numerical simulations of time-dependent problems. It is based on a decomposition of the time interval into subintervals, and on a predictor-corrector strategy, where the propagations over each subinterval for the corrector stage are concurrently performed on the different processors that are available. In this article, we are concerned with the long time integration of Hamiltonian systems. Geometric, structure-preserving integrators are preferably employed for such systems because they show interesting numerical properties, in particular excellent preservation of the total energy of the system. Using a symmetrization procedure and/or a (possibly also symmetric) projection step, we introduce here several variants of the original plain parareal in time algorithm [L. Baffico, et al. Phys. Rev. E 66 (2002) 057701; G. Bal and Y. Maday, A parareal time discretization for nonlinear PDE's with application to the pricing of an American put, in Recent developments in domain decomposition methods, Lect. Notes Comput. Sci. Eng. 23 (2002) 189-202; J.-L. Lions, Y. Maday and G. Turinici, C. R. Acad. Sci. Paris, Série I 332 (2001) 661-668.] that are better adapted to the Hamiltonian context. These variants are compatible with the geometric structure of the exact dynamics, and are easy to implement. Numerical tests on several model systems illustrate the remarkable properties of the proposed parareal integrators over long integration times. Some formal elements of understanding are also provided.
@article{M2AN_2013__47_3_717_0,
author = {Dai, Xiaoying and Le Bris, Claude and Legoll, Fr\'ed\'eric and Maday, Yvon},
title = {Symmetric parareal algorithms for hamiltonian systems},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
volume = {47},
year = {2013},
pages = {717-742},
doi = {10.1051/m2an/2012046},
mrnumber = {3056406},
zbl = {1269.65133},
language = {en},
url = {http://dml.mathdoc.fr/item/M2AN_2013__47_3_717_0}
}
Dai, Xiaoying; Le Bris, Claude; Legoll, Frédéric; Maday, Yvon. Symmetric parareal algorithms for hamiltonian systems. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Tome 47 (2013) pp. 717-742. doi : 10.1051/m2an/2012046. http://gdmltest.u-ga.fr/item/M2AN_2013__47_3_717_0/
[1] , Rattle: a velocity version of the Shake algorithm for molecular dynamics calculations. J. Comput. Phys. 52 (1983) 24-34. | Zbl 0513.65052
[2] , , , and , Parallel in time molecular dynamics simulations. Phys. Rev. E 66 (2002) 057701.
[3] , On the convergence and the stability of the parareal algorithm to solve partial differential equations, in Domain decomposition methods in science and engineering, edited by R. Kornhuber, R. Hoppe, J. Périaux, O. Pironneau, O. Widlund and J. Xu. Springer Verlag, Lect. Notes Comput. Sci. Eng. 40 (2005) 425-432. | MR 2235769 | Zbl 1066.65091
[4] and , A parareal time discretization for nonlinear PDE's with application to the pricing of an American put, in Recent developments in domain decomposition methods, edited by L.F. Pavarino and A. Toselli. Springer Verlag, Lect. Notes Comput. Sci. Eng. 23 (2002) 189-202. | MR 1962689 | Zbl 1022.65096
[5] and , Symplectic parareal, in Domain decomposition methods in science and engineering, edited by U. Langer, M. Discacciati, D.E. Keyes, O.B. Widlund and W. Zulehner. Springer Verlag, Lect. Notes Comput. Sci. Eng. 60 (2008) 401-408. | MR 2436107 | Zbl 1140.65372
[6] and , Parallel algorithms for initial value problems for nonlinear vector difference and differential equations. J. Comput. Appl. Math. 25 (1989) 341-350. | MR 999097 | Zbl 0675.65134
[7] and , On the Hamiltonian interpolation of near to the identity symplectic mappings with application to symplectic integration algorithms. J. Stat. Phys. 74 (1994) 1117-1143. | MR 1268787 | Zbl 0842.58020
[8] , , , , and , Event-based parareal: A data-flow based implementation of parareal. J. Comput. Phys. 231 (2012) 5945-5954.
[9] , Parallel and sequential methods for ordinary differential equations, Numerical Mathematics and Scientific Computation, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York (1995). | MR 1367504 | Zbl 0838.65073
[10] , Parallel methods for ODEs. Advances Comput. Math. 7 (1997) 1-3. | MR 1442045 | Zbl 0880.00022
[11] and , A parallel shooting technique for solving dissipative ODE's. Computing 51(3-4) (1993) 209-236. | MR 1253404 | Zbl 0788.65079
[12] , , and , Symmetric parareal algorithms for Hamiltonian systems, arXiv:preprint 1011.6222. | MR 3056406
[13] , , and , Time-parallel implicit integrators for the near-real-time prediction of linear structural dynamic responses. Int. J. Numer. Meth. Engng. 67 (2006) 697-724. | MR 2241303 | Zbl 1113.74023
[14] , and , A parareal in time semi-implicit approximation of the Navier Stokes equations, in Domain decomposition methods in science and engineering, edited by R. Kornhuber, R. Hoppe, J. Périaux, O. Pironneau, O. Widlund and J. Xu. Springer Verlag Lect. Notes Comput. Sci. Eng. 40 (2005) 433-440. | MR 2235770 | Zbl pre02143574
[15] and , Understanding molecular simulation, from algorithms to applications, 2nd ed., Academic Press (2002). | Zbl 0889.65132
[16] and , On the superlinear and linear convergence of the parareal algorithm, in Proceedings of the 16th International Conference on Domain Decomposition Methods, January 2005, edited by O. Widlund and D. Keyes. Springer, Lect. Notes Comput. Sci. Eng. 55 (2006) 291-298. | MR 2334115 | Zbl 1066.65099
[17] and , Analysis of the parareal time-parallel time-integration method. SIAM J. Sci. Comput. 29 (2007) 556-578. | MR 2306258 | Zbl 1141.65064
[18] , , and , Convergent iterative schemes for time parallelization. Math. Comput. 75 (2006) 1403-1428. | MR 2219035 | Zbl 1089.76038
[19] , Parabolic multigrid methods, Computing methods in applied sciences and engineering VI (Versailles, 1983), North-Holland, Amsterdam (1984) 189-197. | MR 806780 | Zbl 0565.65062
[20] , Symmetric projection methods for differential equations on manifolds. BIT 40 (2000) 726-734. | MR 1799312 | Zbl 0968.65108
[21] and , The life span of backward error analysis for numerical integrators. Numer. Math. 76 (1997) 441-462. | MR 1464151 | Zbl 0874.65061
[22] , and , Geometric numerical integration: structure-preserving algorithms for ordinary differential equations. Springer Ser. Comput. Math. 31 (2002). | MR 1904823 | Zbl 0994.65135
[23] , Numerical methods for elastic wave propagation, in Waves in nonlinear pre-stressed materials, edited by M. Destrade and G. Saccomandi. Springer-Verlag (2007) 181-281. | MR 2389284 | Zbl 1173.74020
[24] , The mathematical model for elastic wave propagation. Effective computational methods for wave propagation, in Numer. Insights, Chapman & Hall/CRC (2008) 247-266. | MR 2404880 | Zbl 1162.74021
[25] , A numerical experiment on the chaotic behavior of the Solar system. Nature 338 (1989) 237-238.
[26] , Chaotic diffusion in the Solar system. Icarus 196 (2008) 1-15.
[27] and , Simulating Hamiltonian dynamics. Cambridge University Press (2004). | MR 2132573 | Zbl 1069.65139
[28] and , Symplectic numerical integrators in constrained Hamiltonian systems. J. Comput. Phys. 112 (1994) 117-125. | MR 1277499 | Zbl 0817.65057
[29] , and , The waveform relaxation method for time-domain analysis of large scale integrated circuits. IEEE Trans. CAD of IC Syst. 1 (1982) 131-145.
[30] , and , A parareal in time discretization of PDE's. C. R. Acad. Sci. Paris, Ser. I 332 (2001) 661-668. | MR 1842465 | Zbl 0984.65085
[31] , The parareal in time algorithm, in Substructuring Techniques and Domain Decomposition Methods, edited by F. Magoulès. Chapt. 2, Saxe-Coburg Publications, Stirlingshire, UK (2010) 19-44. doi:10.4203/csets.24.2
[32] and , A parareal in time procedure for the control of partial differential equations. C. R. Acad. Sci. Paris Ser. I 335 (2002) 387-392. | MR 1931522 | Zbl 1006.65071
[33] and , A parallel in time approach for quantum control: the parareal algorithm. Int. J. Quant. Chem. 93 (2003) 223-228.
[34] and , The parareal in time iterative solver: a further direction to parallel implementation, in Domain decomposition methods in science and engineering, edited by R. Kornhuber, R. Hoppe, J. Périaux, O. Pironneau, O. Widlund and J. Xu. Springer Verlag, Lect. Notes Comput. Sci. Eng. 40 (2005) 441-448. | MR 2235771 | Zbl 1067.65102
[35] and , Domain decomposition methods for partial differential equations, Numerical Mathematics and Scientific Computation, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York (1999). | MR 1857663 | Zbl 0931.65118
[36] , Backward error analysis for numerical integrators. SIAM J. Numer. Anal. 36 (1999) 1549-1570. | MR 1706731 | Zbl 0935.65142
[37] , and , Numerical integration of the cartesian equations of motion of a system with constraints: molecular dynamics of n-alkanes. J. Comput. Phys. 23 (1977) 327-341.
[38] , and , A parallel integration method for Solar system dynamics. Astron. J. 114 (1997) 409-414.
[39] and , Symplectic integrators for solar system dynamics. Astron. J. 104 (1992) 1633-1640.
[40] and , Numer. Hamiltonian Problems. Chapman & Hall (1994). | MR 1270017 | Zbl 0816.65042
[41] and , Stability of the parareal algorithm, in Domain decomposition methods in science and engineering, edited by R. Kornhuber, R. Hoppe, J. Périaux, O. Pironneau, O. Widlund and J. Xu. Springer Verlag, Lect. Notes Comput. Sci. Eng. 40 (2005) 449-456. | MR 2235772 | Zbl 1066.65079
[42] and , Domain decomposition methods-algorithms and theory. Springer Ser. Comput. Math. 34 (2005). | MR 2104179 | Zbl 1069.65138