Symmetric parareal algorithms for hamiltonian systems

Xiaoying Dai; Claude Le Bris; Frédéric Legoll; Yvon Maday

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique (2013)

  • Volume: 47, Issue: 3, page 717-742
  • ISSN: 0764-583X

Abstract

top
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.

How to cite

top

Dai, Xiaoying, et al. "Symmetric parareal algorithms for hamiltonian systems." ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique 47.3 (2013): 717-742. <http://eudml.org/doc/273346>.

@article{Dai2013,
abstract = {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.},
author = {Dai, Xiaoying, Le Bris, Claude, Legoll, Frédéric, Maday, Yvon},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique},
keywords = {parallel integrators; hamiltonian dynamics; long-time integration; symmetric algorithms; symmetric projection; geometric integration; Hamiltonian dynamics; numerical examples; structure-preserving integrators},
language = {eng},
number = {3},
pages = {717-742},
publisher = {EDP-Sciences},
title = {Symmetric parareal algorithms for hamiltonian systems},
url = {http://eudml.org/doc/273346},
volume = {47},
year = {2013},
}

TY - JOUR
AU - Dai, Xiaoying
AU - Le Bris, Claude
AU - Legoll, Frédéric
AU - Maday, Yvon
TI - Symmetric parareal algorithms for hamiltonian systems
JO - ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique
PY - 2013
PB - EDP-Sciences
VL - 47
IS - 3
SP - 717
EP - 742
AB - 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.
LA - eng
KW - parallel integrators; hamiltonian dynamics; long-time integration; symmetric algorithms; symmetric projection; geometric integration; Hamiltonian dynamics; numerical examples; structure-preserving integrators
UR - http://eudml.org/doc/273346
ER -

References

top
  1. [1] H.C. Andersen, Rattle: a velocity version of the Shake algorithm for molecular dynamics calculations. J. Comput. Phys.52 (1983) 24–34. Zbl0513.65052
  2. [2] L. Baffico, S. Bernard, Y. Maday, G. Turinici and G. Zérah, Parallel in time molecular dynamics simulations. Phys. Rev. E 66 (2002) 057701. 
  3. [3] G. Bal, 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. Zbl1066.65091MR2235769
  4. [4] 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, edited by L.F. Pavarino and A. Toselli. Springer Verlag, Lect. Notes Comput. Sci. Eng. 23 (2002) 189–202. Zbl1022.65096MR1962689
  5. [5] G. Bal and Q. Wu, 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. Zbl1140.65372MR2436107
  6. [6] A. Bellen and M. Zennaro, Parallel algorithms for initial value problems for nonlinear vector difference and differential equations. J. Comput. Appl. Math.25 (1989) 341–350. Zbl0675.65134MR999097
  7. [7] G. Benettin and A. Giorgilli, On the Hamiltonian interpolation of near to the identity symplectic mappings with application to symplectic integration algorithms. J. Stat. Phys.74 (1994) 1117–1143. Zbl0842.58020MR1268787
  8. [8] L.A. Berry, W. Elwasif, J.M. Reynolds-Barredo, D. Samaddar, R. Sanchez and D.E. Newman, Event-based parareal: A data-flow based implementation of parareal. J. Comput. Phys.231 (2012) 5945–5954. 
  9. [9] K. Burrage, 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). Zbl0838.65073MR1367504
  10. [10] K. Burrage, Parallel methods for ODEs. Advances Comput. Math.7 (1997) 1–3. Zbl0880.00022MR1442045
  11. [11] P. Chartier and B. Philippe, A parallel shooting technique for solving dissipative ODE’s. Computing 51(3-4) (1993) 209–236. Zbl0788.65079MR1253404
  12. [12] X. Dai, C. Le Bris, F. Legoll and Y. Maday, Symmetric parareal algorithms for Hamiltonian systems, arXiv:preprint 1011.6222. Zbl1269.65133MR3056406
  13. [13] C. Farhat, J. Cortial, C. Dastillung and H. Bavestrello, Time-parallel implicit integrators for the near-real-time prediction of linear structural dynamic responses. Int. J. Numer. Meth. Engng.67 (2006) 697–724. Zbl1113.74023MR2241303
  14. [14] P. Fischer, F. Hecht and Y. Maday, 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. Zbl1309.76060MR2235770
  15. [15] D. Frenkel and B. Smit, Understanding molecular simulation, from algorithms to applications, 2nd ed., Academic Press (2002). Zbl0889.65132
  16. [16] M. Gander and S. Vandewalle, 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. Zbl1066.65099MR2334115
  17. [17] M. Gander and S. Vandewalle, Analysis of the parareal time-parallel time-integration method. SIAM J. Sci. Comput.29 (2007) 556–578. Zbl1141.65064MR2306258
  18. [18] I. Garrido, B. Lee, G.E. Fladmark and M.S. Espedal, Convergent iterative schemes for time parallelization. Math. Comput.75 (2006) 1403–1428. Zbl1089.76038MR2219035
  19. [19] W. Hackbusch, Parabolic multigrid methods, Computing methods in applied sciences and engineering VI (Versailles, 1983), North-Holland, Amsterdam (1984) 189–197. Zbl0565.65062MR806780
  20. [20] E. Hairer, Symmetric projection methods for differential equations on manifolds. BIT40 (2000) 726–734. Zbl0968.65108MR1799312
  21. [21] E. Hairer and C. Lubich, The life span of backward error analysis for numerical integrators. Numer. Math.76 (1997) 441–462. Zbl0874.65061MR1464151
  22. [22] E. Hairer, C. Lubich and G. Wanner, Geometric numerical integration: structure-preserving algorithms for ordinary differential equations. Springer Ser. Comput. Math. 31 (2002). Zbl0994.65135MR1904823
  23. [23] P. Joly, 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. Zbl1173.74020MR2389284
  24. [24] P. Joly, The mathematical model for elastic wave propagation. Effective computational methods for wave propagation, in Numer. Insights, Chapman & Hall/CRC (2008) 247–266. Zbl1162.74021MR2404880
  25. [25] J. Laskar, A numerical experiment on the chaotic behavior of the Solar system. Nature338 (1989) 237–238. 
  26. [26] J. Laskar, Chaotic diffusion in the Solar system. Icarus196 (2008) 1–15. 
  27. [27] B. Leimkuhler and S. Reich, Simulating Hamiltonian dynamics. Cambridge University Press (2004). Zbl1069.65139MR2132573
  28. [28] B.J. Leimkuhler and R.D. Skeel, Symplectic numerical integrators in constrained Hamiltonian systems. J. Comput. Phys.112 (1994) 117–125. Zbl0817.65057MR1277499
  29. [29] E. Lelarasmee, A.E. Ruehli and A.L. Sangiovanni-Vincentelli, The waveform relaxation method for time-domain analysis of large scale integrated circuits. IEEE Trans. CAD of IC Syst.1 (1982) 131–145. 
  30. [30] J.-L. Lions, Y. Maday and G. Turinici, A parareal in time discretization of PDE’s. C. R. Acad. Sci. Paris, Ser. I 332 (2001) 661–668. Zbl0984.65085MR1842465
  31. [31] Y. Maday, 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. [32] Y. Maday and G. Turinici, A parareal in time procedure for the control of partial differential equations. C. R. Acad. Sci. Paris Ser. I335 (2002) 387–392. Zbl1006.65071MR1931522
  33. [33] Y. Maday and G. Turinici, A parallel in time approach for quantum control: the parareal algorithm. Int. J. Quant. Chem.93 (2003) 223–228. 
  34. [34] Y. Maday and G. Turinici, 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. Zbl1067.65102MR2235771
  35. [35] A. Quarteroni and A. Valli, Domain decomposition methods for partial differential equations, Numerical Mathematics and Scientific Computation, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York (1999). Zbl0931.65118MR1857663
  36. [36] S. Reich, Backward error analysis for numerical integrators. SIAM J. Numer. Anal.36 (1999) 1549–1570. Zbl0935.65142MR1706731
  37. [37] J.-P. Ryckaert, G. Ciccotti and H.J.C. Berendsen, 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. [38] P. Saha, J. Stadel and S. Tremaine, A parallel integration method for Solar system dynamics. Astron. J.114 (1997) 409–414. 
  39. [39] P. Saha and S. Tremaine, Symplectic integrators for solar system dynamics. Astron. J.104 (1992) 1633–1640. 
  40. [40] J.M. Sanz-Serna and M.P. Calvo, Numer. Hamiltonian Problems. Chapman & Hall (1994). Zbl0816.65042MR1270017
  41. [41] G.A. Staff and E.M. Rønquist, 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. Zbl1066.65079MR2235772
  42. [42] A. Toselli and O. Widlund, Domain decomposition methods–algorithms and theory. Springer Ser. Comput. Math. 34 (2005). Zbl1069.65138MR2104179

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.