A hybrid algorithm based on parareal and Schwarz waveform relaxation

Liping Yang; Hu Li; Liping Yang; Hu Li

doi:10.3934/era.2022207

Electronic Research Archive

2022, Volume 30, Issue 11: 4086-4107. doi: 10.3934/era.2022207

Previous Article Next Article

Research article Special Issues

A hybrid algorithm based on parareal and Schwarz waveform relaxation

Liping Yang ¹,
Hu Li ^{2
,
,}

1.
Department of Mathematics, Zigong Vocational and Technical College, Zigong 643000, China
2.
School of Mathematics, Chengdu Normal University, Chengdu 611130, China

Received: 28 June 2022 Revised: 09 August 2022 Accepted: 11 August 2022 Published: 16 September 2022

In this paper, we present a hybrid algorithm based on parareal and Schwarz waveform relaxation (SWR) for solving time dependent partial differential equations. The parallelism can be simultaneously realized in the time direction by using a parareal and in the space direction via SWR. We give a convergence analysis for the hybrid algorithm for a 1D model problem, the reaction-diffusion equation. Weak scaling of the algorithm in terms of both the number of space subdomains and the number of paralleled time intervals were investigated via theoretical analysis and numerical experiments.
- Schwarz waveform relaxation (SWR),
- parareal algorithm,
- convergence analysis,
- weak scaling,
- domain decomposition
Citation: Liping Yang, Hu Li. A hybrid algorithm based on parareal and Schwarz waveform relaxation[J]. Electronic Research Archive, 2022, 30(11): 4086-4107. doi: 10.3934/era.2022207

Related Papers:

Abstract

In this paper, we present a hybrid algorithm based on parareal and Schwarz waveform relaxation (SWR) for solving time dependent partial differential equations. The parallelism can be simultaneously realized in the time direction by using a parareal and in the space direction via SWR. We give a convergence analysis for the hybrid algorithm for a 1D model problem, the reaction-diffusion equation. Weak scaling of the algorithm in terms of both the number of space subdomains and the number of paralleled time intervals were investigated via theoretical analysis and numerical experiments.

References

[1]	A. Toselli, O. Widlund, Domain Decomposition Methods: Algorithms and Theory, Springer, Berlin, 2005.
[2]	T. P. A. Mathew, Domain Decomposition Methods for the Numerical Solution of Partial Differential Equations, Springer-Verlag, Berlin, 2008.
[3]	X. C. Cai, Additive Schwarz algorithms for parabolic convection-diffusion equations, Numer. Math., 60 (1991), 41-61. https://doi.org/10.1007/BF01385713 doi: 10.1007/BF01385713
[4]	X. C. Cai, Multiplicative Schwarz methods for parabolic problems, SIAM J. Sci. Comput., 15 (1994), 587-603. https://doi.org/10.1137/0915039 doi: 10.1137/0915039
[5]	L. Qin, X. J. Xu, Optimized Schwarz methods with Robin transmission conditions for parabolic problems, SIAM J. Sci. Comput., 31 (2008), 608-623. https://doi.org/10.1137/070682149 doi: 10.1137/070682149
[6]	M. Al-Khaleel, S. L. Wu, Quasi-overlapping semi-discrete Schwarz waveform relaxation algorithms: The hyperbolic problem, Comput. Methods Appl. Math., 20 (2020), 397-417. https://doi.org/10.1515/cmam-2018-0188 doi: 10.1515/cmam-2018-0188
[7]	D. Bennequin, M. J. Gander, L. Gouarin, L. Halpern, Optimized Schwarz waveform relaxation for advection reaction diffusion equations in two dimensions, Numer. Math., 134 (2016), 513-567. https://doi.org/10.1007/s00211-015-0784-8 doi: 10.1007/s00211-015-0784-8
[8]	D. Bennequin, M. J. Gander, L. Halpern, A homographic best approximation problem with application to optimized Schwarz waveform relaxation, Math. Comput., 78 (2009), 185-223. https://doi.org/10.1090/S0025-5718-08-02145-5 doi: 10.1090/S0025-5718-08-02145-5
[9]	M. J. Gander, L. Halpern, Optimized Schwarz waveform relaxation for advection reaction diffusion problems, SIAM J. Numer. Anal., 45 (2007), 666-697. https://doi.org/10.1007/s00211-015-0784-8 doi: 10.1007/s00211-015-0784-8
[10]	M. J. Gander, A. M. Stuart, Space-time continuous analysis of waveform relaxation for the heat equation, SIAM J. Sci. Comput., 19 (1998), 2014-2031. https://doi.org/10.1137/S1064827596305337 doi: 10.1137/S1064827596305337
[11]	E. Giladi, H. B. Keller, Space-time domain decomposition for parabolic problems, Numer. Math., 93 (2002), 279-313. https://doi.org/10.1007/s002110100345 doi: 10.1007/s002110100345
[12]	S. L. Wu, M. D. Al-Khaleel, Semi-discrete Schwarz waveform relaxation algorithms for reaction diffusion equations, BIT Numer. Math., 54 (2014), 831-866. https://doi.org/10.1007/s10543-014-0475-3 doi: 10.1007/s10543-014-0475-3
[13]	S. L. Wu, M. D. Al-Khaleel, Convergence analysis of the Neumann-Neumann waveform relaxation method for time-fractional RC circuits, Simul. Model. Pract. Theory, 64 (2016), 43-56. https://doi.org/10.1016/j.simpat.2016.01.002 doi: 10.1016/j.simpat.2016.01.002
[14]	J. L. Lions, Y. Maday, G. Turinici, Résolution d'EDP par un schéma en temps pararéel, C. R. Acad. Sci. Paris Sér. I Math., 332 (2001), 661-668. https://doi.org/10.1016/S0764-4442(00)01793-6 doi: 10.1016/S0764-4442(00)01793-6
[15]	M. Cai, J. Mahseredjian, I. Kocar, X. Fu, A. Haddadi, A parallelization-in-time approach for accelerating EMT simulations, Electr. Power Syst. Res., 197 (2021), 107346. https://doi.org/10.1016/j.epsr.2021.107346 doi: 10.1016/j.epsr.2021.107346
[16]	T. Cheng, N. Lin, V. Dinavahi, Hybrid parallel-in-time-and-space transient stability simulation of large-ccale AC/DC grids, IEEE Trans. Power Syst., in press, 2022. https://doi.org/10.1109/TPWRS.2022.3153450
[17]	I. C. Garcia, I. Kulchytska-Ruchka, S. Schops, Parareal for index two differential algebraic equations, Numer. Alg., 91 (2022), 389-412. https://doi.org/10.1007/s11075-022-01267-1 doi: 10.1007/s11075-022-01267-1
[18]	E. Celledoni, T. Kvamsdal, Parallelization in time for thermo-viscoplastic problems in extrusion of aluminium, Int. J. Numer. Methods Eng., 79 (2009), 576-598. https://doi.org/10.1002/nme.2585 doi: 10.1002/nme.2585
[19]	D. Max, M. Marc, D. Stéphane, Parareal operator splitting techniques for multi-scale reaction waves: numerical analysis and strategies, ESAIM Math. Model. Numer. Anal., 45 (2011), 825-852. https://doi.org/10.1051/m2an/2010104 doi: 10.1051/m2an/2010104
[20]	L. Fang, S. Vandewalle, J. Meyers, A parallel-in-time multiple shooting algorithm for large-scale PDE-constrained optimal control problems, J. Comput. Phys., 452 (2021), 110926. https://doi.org/10.1016/j.jcp.2021.110926 doi: 10.1016/j.jcp.2021.110926
[21]	M. J. Gander, F. Kwok, J. Salomon, PARAOPT: a parareal algorithm for optimality systems, SIAM J. Sci. Comput., 42 (2020), A2773-A2802. https://doi.org/10.1137/19M1292291 doi: 10.1137/19M1292291
[22]	Y. Maday, M. K. Riahi, J. Salomon, Parareal in time intermediate targets methods for optimal control problems, in Control and Optimization with PDE Constraints, Birkhäuser, Basel, 164 (2013), 79-92. https://doi.org/10.1007/978-3-0348-0631-2_5
[23]	M. K. Riahi, J. Salomon, S. J. Glaser, D. Sugny, Fully efficient time-parallelized quantum optimal control algorithm, Phys. Rev. A, 93 (2016), 043410. https://doi.org/10.1103/PhysRevA.93.043410 doi: 10.1103/PhysRevA.93.043410
[24]	X. M. Gu, S. L. Wu, A parallel-in-time iterative algorithm for Volterra partial integro-differential problems with weakly singular kernel, J. Comput. Phys., 417 (2020), 109576. https://doi.org/10.1016/j.jcp.2020.109576 doi: 10.1016/j.jcp.2020.109576
[25]	X. M. Gu, Y. L. Zhao, X. L. Zhao, B. Carpentieri, Y. Y. Huang, A note on parallel preconditioning for the all-at-once solution of Riesz fractional diffusion equations, Numer. Math. Theor. Meth. Appl., 14 (2021), 893-919. https://doi.org/10.4208/nmtma.OA-2020-0020 doi: 10.4208/nmtma.OA-2020-0020
[26]	Y. L. Zhao, P. Y. Zhu, X. M. Gu, X. L. Zhao, H. Y. Jian, A preconditioning technique for all-at-once system from the nonlinear tempered fractional diffusion equation, J. Sci. Comput., 83 (2020), 10. https://doi.org/10.1007/s10915-020-01193-1 doi: 10.1007/s10915-020-01193-1
[27]	M. J. Gander, S. Vandewalle, Analysis of the parareal time-parallel time-integration method, SIAM J. Sci. Comput., 29 (2007), 556-578. https://doi.org/10.1137/05064607X doi: 10.1137/05064607X
[28]	M. J. Gander, S. L. Wu, A diagonalization-based parareal algorithm for dissipative and wave propagation problems, SIAM J. Numer. Anal., 58 (2020), 2981-3009. https://doi.org/10.1137/19M1271683 doi: 10.1137/19M1271683
[29]	S. L. Wu, Toward parallel coarse grid correction for the parareal algorithm, SIAM J. Sci. Comput., 40 (2018), A1446-A1472. https://doi.org/10.1137/17M1141102 doi: 10.1137/17M1141102
[30]	S. L. Wu, T. Zhou, Convergence analysis for three parareal solvers, SIAM J. Sci. Comput., 37 (2015), A970-A992. https://doi.org/10.1137/140970756 doi: 10.1137/140970756
[31]	T. Cadeau, F. Mafoules, Coupling the parareal algorithm with the waveform relaxation method for the solution of differential algebraic equations, in 10th International Symposium on Distributed Computing and Applications to Business, Engineering and Science, (2011), 15-19. https://doi.org/10.1109/DCABES.2011.34
[32]	Y. L. Jiang, B. Song, Coupling parareal and Dirichlet-Neumann/Neumann-Neumann waveform relaxation methods for the heat equation, in International Conference on Domain Decomposition Methods, Springer, Cham, 125 (2018), 405-413. https://doi.org/10.1007/978-3-319-93873-8_38
[33]	T. Cadeau, F. Magoulès, Coupling parareal and waveform relaxation methods for power systems, in IEEE International Conference on Electrical and Control Engineering, (2011), 2947-2950. https://doi.org/10.1109/ICECENG.2011.6057305
[34]	J. Li, Y. L. Jiang, Z. Miao, A parareal approach of semi-linear parabolic equations based on general waveform relaxation, Numer. Methods Partial Differ. Equations, 35 (2019), 2017-2043. https://doi.org/10.1002/num.22390 doi: 10.1002/num.22390
[35]	J. Liu, Y. L. Jiang, A parareal algorithm based on waveform relaxation, Math. Comput. Simul. 82 (2012), 2167-2181. https://doi.org/10.1016/j.matcom.2012.05.017
[36]	J. Liu, Y. L. Jiang, A parareal waveform relaxation algorithm for semi-linear parabolic partial differential equations, J. Comput. Appl. Math., 236 (2012), 4245-4263. https://doi.org/10.1016/j.cam.2012.05.014 doi: 10.1016/j.cam.2012.05.014
[37]	B. Song, Y. L. Jiang, Analysis of a new parareal algorithm based on waveform relaxation method for time-periodic problems, Numer. Algorithms, 67 (2014), 599-622. https://doi.org/10.1007/s11075-013-9810-z doi: 10.1007/s11075-013-9810-z
[38]	B. Song, Y. L. Jiang, A new parareal waveform relaxation algorithm for time-periodic problems, Int. J. Comput. Math., 92 (2015), 377-393. https://doi.org/10.1080/00207160.2014.891734 doi: 10.1080/00207160.2014.891734
[39]	B. Song, Y. L. Jiang, X. Wang, Analysis of two new parareal algorithms based on the Dirichlet-Neumann/Neumann-Neumann waveform relaxation method for the heat equation, Numer. Algorithms, 6 (2021), 1685-1703. https://doi.org/10.1007/s11075-020-00949-y doi: 10.1007/s11075-020-00949-y
[40]	E. Lelarasmee, A. E. Ruehli, A. L. Sangiovanni-Vincentelli, The waveform relaxation methods for time-domain analysis of large scale integrated circuits, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 1 (1982), 131-145. https://doi.org/10.1109/TCAD.1982.1270004 doi: 10.1109/TCAD.1982.1270004
[41]	D. Q. Bui, C. Japhet, Y. Maday, P. Omnes, Coupling parareal with optimized Schwarz waveform relaxation for parabolic problems, SIAM J. Numer. Anal., 60 (2022), 913-9399. https://doi.org/10.1137/21M1419428 doi: 10.1137/21M1419428
[42]	M. J. Gander, Y. Jiang, R. Li, Parareal Schwarz waveform relaxation methods, in Domain Decomposition Methods in Science and Engineering XX, Springer, Berlin, Heidelberg, 91 (2012), 451-458. https://doi.org/10.1007/978-3-642-35275-1_53
[43]	M. Gander, Y. Jiang, B. Song, A superlinear convergence estimate for the parareal Schwarz waveform relaxation algorithm, SIAM J. Sci. Comput., 41 (2019), A1148-A1169. https://doi.org/10.1137/18M1177226 doi: 10.1137/18M1177226
[44]	M. J. Gander, M. Al-Khaleel, A. Ruehli, Optimized waveform relaxation methods for the longitudinal partitioning of transmission lines, IEEE Trans. Circuits Syst. I Regul. Pap., 56 (2009), 1732-1743. https://doi.org/10.1109/TCSI.2008.2008286 doi: 10.1109/TCSI.2008.2008286
[45]	R. S. Varga, Matrix Iterative Analysis, 2$^{nd}$ edition, Spring-Verlag, Berlin Heidelberg, 2000.

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)