On "Optimal" h-Independent Convergence of Parareal and MGRIT using Runge-Kutta Time Integration

DOI10.1002/NLA.2301arXiv1906.06672MaRDI QIDQ6320564FDOQ6320564

Authors: S. Friedhoff, Ben S. Southworth 

Publication date: 16 June 2019

Abstract: Although convergence of the Parareal and multigrid-reduction-in-time (MGRIT) parallel-in-time algorithms is well studied, results on their optimality is limited. Appealling to recently derived tight bounds of two-level Parareal and MGRIT convergence, this paper proves (or disproves) $h_x$- and $h_t$-independent convergence of two-level Parareal and MGRIT, for linear problems of the form $mathbf{u}^{\prime }(t)+mathcalLmathbfu(t)=f(t)$, where $mathcalL$ is symmetric positive definite and Runge-Kutta time integration is used. The theory presented in this paper also encompasses analysis of some modified Parareal algorithms, such as the $heta$-Parareal method, and shows that not all Runge-Kutta schemes are equal from the perspective of parallel-in-time. Some schemes, particularly L-stable methods, offer significantly better convergence than others as they are guaranteed to converge rapidly at both limits of small and large $h_{t}xi$, where $xi$ denotes an eigenvalue of $mathcalL$ and $h_t$ time-step size. On the other hand, some schemes do not obtain $h$-optimal convergence, and two-level convergence is restricted to certain regimes. In certain cases, an $mathcalO(1)$ factor change in time step $h_t$ or coarsening factor $k$ can be the difference between convergence factors $hoapprox0.02$ and divergence! The analysis is extended to skew symmetric operators as well, which cannot obtain $h$-independent convergence and, in fact, will generally not converge for a sufficiently large number of time steps. Numerical results confirm the analysis in practice and emphasize the importance of a priori analysis in choosing an effective coarse-grid scheme and coarsening factor. A Mathematica notebook to perform a priori two-grid analysis is available at https://github.com/XBraid/xbraid-convergence-est.

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations (65L06)

This page was built for publication: On "Optimal" h-Independent Convergence of Parareal and MGRIT using Runge-Kutta Time Integration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6320564)