Top

Numerical Algorithms

Published in:

13-06-2020 | Original Paper

Analysis of two new parareal algorithms based on the Dirichlet-Neumann/Neumann-Neumann waveform relaxation method for the heat equation

Authors: Bo Song, Yao-Lin Jiang, Xiaolong Wang

Published in: Numerical Algorithms | Issue 4/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The Dirichlet-Neumann and Neumann-Neumann waveform relaxation methods are nonoverlapping spatial domain decomposition methods to solve evolution problems, while the parareal algorithm is in time parallel fashion. Based on the combinations of these space and time parallel strategies, we present and analyze two parareal algorithms based on the Dirichlet-Neumann and the Neumann-Neumann waveform relaxation method for the heat equation by choosing Dirichlet-Neumann/Neumann-Neumann waveform relaxation as two new kinds of fine propagators instead of the classical fine propagator. Both new proposed algorithms could be viewed as a space-time parallel algorithm, which increases the parallelism both in space and in time. We derive for the heat equation the convergence results for both algorithms in one spatial dimension. We also illustrate our theoretical results with numerical experiments finally.

previous article Nonmonotone inexact restoration approach for minimization with orthogonality constraints

next article A new method for solving split equality problems via projection dynamical systems

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Baffico, L., Bernard, S., Maday, Y., Turinici, G., Zérah, G.: Parallel-in-time molecular-dynamics simulations. Phys. Rev. E 66, 057701 (2002)CrossRef

Bal, G.: Parallelization in time of (stochastic) ordinary differential equations. Math. Meth. Anal Num. (submitted) (2003)

Engblom, S.: Parallel in time simulation of multiscale stochastic chemical kinetics. Multiscale Model. Simul. 8(1), 46–68 (2009)MathSciNetCrossRef

Fischer, P.F., Hecht, F., Maday, Y.: A parareal in time semi-implicit approximation of the Navier-Stokes equations. In: Kornhuber, R. et al. (eds.) Domain Decomposition Methods in Science and Engineering, Lecture Notes in Computational Science and Engineering, vol. 40, pp 433–440. Springer, Berlin (2005)

Gander, M.J.: 50 years of time parallel time integration. In: Multiple Shooting and Time Domain Decomposition Methods, pp 69–113. Springer (2015)

Gander, M.J., Hairer, E.: Nonlinear convergence analysis for the parareal algorithm. Lect. Notes Comput. Sci. Eng. 60, 45–56 (2008)MathSciNetCrossRef

Gander, M.J., Halpern, L.: Optimized Schwarz waveform relaxation methods for advection reaction diffusion problems. SIAM J. Numer. Anal. 45(2), 666–697 (2007)MathSciNetCrossRef

Gander, M.J., Halpern, L., Nataf, F.: Optimal Schwarz waveform relaxation for the one dimensional wave equation. SIAM J. Numer. Anal. 41(5), 1643–1681 (2003)MathSciNetCrossRef

Gander, M.J., Jiang, Y.L., Li, R.J.: Parareal Schwarz waveform relaxation methods. In: Domain Decomposition Methods in Science and Engineering XX, pp 451–458. Springer (2013)

10.

Gander, M.J., Jiang, Y.L., Song, B.: A superlinear convergence estimate for the parareal Schwarz waveform relaxation algorithm. SIAM J. Sci. Comput. 41 (2), A1148–A1169 (2019)MathSciNetCrossRef

11.

Gander, M.J., Jiang, Y.L., Song, B., Zhang, H.: Analysis of two parareal algorithms for time-periodic problems. SIAM J. Sci. Comput. 35(5), A2393–A2415 (2013)MathSciNetCrossRef

12.

Gander, M.J., Kwok, F., Mandal, B.C.: Dirichlet-Neumann and Neumann-Neumann waveform relaxation algorithms for parabolic problems. Electron. Trans. Numer. Anal. 45, 424–456 (2016)MathSciNetMATH

13.

Gander, M.J., Kwok, F., Mandal, B.C.: Dirichlet-Neumann and Neumann-Neumann waveform relaxation for the wave equation. In: Domain Decomposition Methods in Science and Engineering XXII, pp 501–509. Springer (2016)

14.

Gander, M.J., Stuart, A.M.: Space-time continuous analysis of waveform relaxation for the heat equation. SIAM J. Sci. Comput. 19(6), 2014–2031 (1998)MathSciNetCrossRef

15.

Gander, M.J., Vandewalle, S.: Analysis of the parareal time-parallel time-integration method. SIAM J. Sci. Comput. 29(2), 556–578 (2007)MathSciNetCrossRef

16.

Giladi, E., Keller, H.B.: Space-time domain decomposition for parabolic problems. Numer. Math. 93(2), 279–313 (2002)MathSciNetCrossRef

17.

Jiang, Y.L.: A general approach to waveform relaxation solutions of nonlinear differential-algebraic equations: the continuous-time and discrete-time cases. IEEE Trans. Circ. Syst. I: Regular Papers 51(9), 1770–1780 (2004)MathSciNetCrossRef

18.

Jiang, Y.L.: Waveform Relaxation Methods. Scientific Press, Beijing (2010)

19.

Jiang, Y.L., Ding, X.L.: Waveform relaxation methods for fractional differential equations with the Caputo derivatives. J. Comput. Appl. Math. 238, 51–67 (2013)MathSciNetCrossRef

20.

Jiang, Y.L., Song, B.: Coupling parareal and Dirichlet-Neumann/Neumann-Neumann waveform relaxation methods for the heat equation. In: International Conference on Domain Decomposition Methods, pp 405–413. Springer (2017)

21.

Lelarasmee, E., Ruehli, A.E., Sangiovanni-Vincentelli, A.L.: The waveform relaxation method for time-domain analysis of large scale integrated circuits. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 1(3), 131–145 (1982)CrossRef

22.

Lions, J.L., Maday, Y., Turinici, G.: A “parareal” in time discretization of PDE’s. Comptes Rendus de l’Académie des Sciences-Series I-Mathematics 332(7), 661–668 (2001)CrossRef

23.

Liu, J., Jiang, Y.L.: Waveform relaxation for reaction-diffusion equations. J. Comput. Appl. Mathe. 235(17), 5040–5055 (2011)MathSciNetCrossRef

24.

Liu, J., Jiang, Y.L.: A parareal algorithm based on waveform relaxation. Math. Comput. Simul. 82(11), 2167–2181 (2012)MathSciNetCrossRef

25.

Liu, J., Jiang, Y.L.: A parareal waveform relaxation algorithm for semi-linear parabolic partial differential equations. J. Comput. Appl. Math. 236(17), 4245–4263 (2012)MathSciNetCrossRef

26.

Lubich, C., Ostermann, A.: Multi-grid dynamic iteration for parabolic equations. BIT Numer. Math. 27(2), 216–234 (1987)CrossRef

27.

Maday, Y., Salomon, J., Turinici, G.: Monotonic parareal control for quantum systems. SIAM J. Numer. Anal. 45(6), 2468–2482 (2007)MathSciNetCrossRef

28.

Maday, Y., Turinici, G.: A parareal in time procedure for the control of partial differential equations. Comptes Rendus de l’Académie des Sciences-Series I-Mathematics 335(4), 387–392 (2002)MathSciNetMATH

29.

Maday, Y., Turinici, G.: Parallel in time algorithms for quantum control: parareal time discretization scheme. Int. J. Quant. Chem. 93(3), 223–228 (2003)CrossRef

30.

Maday, Y., Turinici, G.: The parareal in time iterative solver: a further direction to parallel implementation. Lect. Notes Comput. Sci. Eng. 40, 441–448 (2005)MathSciNetCrossRef

31.

Song, B., Jiang, Y.L.: Analysis of a new parareal algorithm based on waveform relaxation method for time-periodic problems. Numer. Algor. 67(3), 599–622 (2014)MathSciNetCrossRef

32.

Song, B., Jiang, Y.L.: A new parareal waveform relaxation algorithm for time-periodic problems. Int. J. Comput. Math. 92(2), 377–393 (2015)MathSciNetCrossRef

33.

Staff, G.: Convergence and Stability of the Parareal Algorithm. Master’s thesis. Norwegian University of Science and Technology, Norway (2003)

34.

Staff, G.A., Rønquist, E.M.: Stability of the parareal algorithm. Domain Decomposition Methods in Science and Engineering 40, 449–456 (2005)MathSciNetCrossRef

35.

Trindade, J.M.F., Pereira, J.C.F.: Parallel-in-time simulation of the unsteady Navier-Stokes equations for incompressible flow. Int. J. Numer. Methods Fluids 45 (10), 1123–1136 (2004)CrossRef

36.

Vandewalle, S., Van de Velde, E.: Space-time concurrent multigrid waveform relaxation. Annals Numer. Math 1, 347–363 (1994)

37.

Wu, S.L.: Toward parallel coarse grid correction for the parareal algorithm. SIAM J. Sci. Comput. 40(3), A1446–A1472 (2018)MathSciNetCrossRef

38.

Wu, S.L., Al-Khaleel, M.: Convergence analysis of the Neumann-Neumann waveform relaxation method for time-fractional RC circuits. Simul. Model. Pract. Theory 64, 43–56 (2016)CrossRef

39.

Wu, S.L., Zhou, T.: Fast parareal iterations for fractional diffusion equations. J. Comput. Phys. 329, 210–226 (2017)MathSciNetCrossRef

Title: Analysis of two new parareal algorithms based on the Dirichlet-Neumann/Neumann-Neumann waveform relaxation method for the heat equation
Authors: Bo Song
Yao-Lin Jiang
Xiaolong Wang
Publication date: 13-06-2020
Publisher: Springer US
Published in: Numerical Algorithms / Issue 4/2021
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265
DOI: https://doi.org/10.1007/s11075-020-00949-y

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 4/2021

A novel alternating-direction implicit spectral Galerkin method for a multi-term time-space fractional diffusion equation in three dimensions

A two-step modulus-based matrix splitting iteration method for horizontal linear complementarity problems

Analysis of optimal superconvergence of the local discontinuous Galerkin method for nonlinear fourth-order boundary value problems

On equivalence of three-parameter iterative methods for singular symmetric saddle-point problem

Unconditional optimal error estimates of linearized backward Euler Galerkin FEMs for nonlinear Schrödinger-Helmholtz equations

A two-grid method for discontinuous Galerkin approximations to nonlinear Sobolev equations

Premium Partner