2019/06/16 by Friedhoff, Stephanie, Southworth, Ben S.
#FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.1906.06672
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) hx- and ht-independent convergence of two-level Parareal and MGRIT, for linear problems of the form u'(t) + Lu(t) = f(t), where L 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 θ-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 htξ, where ξ denotes an eigenvalue of L and ht 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 O(1) factor change in time step ht or coarsening factor k can be the difference between convergence factors ρ≈0.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.