Convergence Analysis for Three Parareal Solvers

Abstract

We analyze in this paper the convergence properties of the parareal algorithm for the symmetric positive definite problem $\mathbf{u}'+A\mathbf{u}=g$. The coarse propagator $\mathcal{G}$ is fixed to the backward-Euler method and three time integrators are chosen for the $\mathcal{F}$-propagator: the trapezoidal rule, the third-order diagonal implicit Runge--Kutta (RK) (DIRK) method, and the fourth-order Gauss RK method. It is well known that the Parareal-Euler algorithm using the backward-Euler method for $\mathcal{F}$ and $\mathcal{G}$ converges rapidly, but less is known when one uses for $\mathcal{F}$ the trapezoidal rule, or the fourth-order Gauss RK method, especially when the mesh ratio $J(=\Delta T/\Delta t)$ is small. We show that for a specified $\lambda_{\max}$(the maximal eigenvalue of $A$ or its upper bound), there exists some critical $J_{\rm cri}$ such that the parareal solvers derived from these three choices of $\mathcal{F}$ converge as fast as Parareal-Euler, provided $J\geq J_{\rm cri}$. Precisely, for $\mathcal{F}$ the trapezoidal rule and the fourth-order Gauss RK method, $J_{\rm cri}$ depends on $\Delta T, \Delta t$, and $\lambda_{\max}$ and we present concise formulas to calculate $J_{cri}$, while for $\mathcal{F}$ the third-order DIRK method, $J_{cri}=4$, independently of these parameters. Numerical examples with applications in fractional PDEs and uncertainty quantification are presented to support the theoretical predictions.