Ben Southworth (University of Colorado, Boulder)
Parareal and multigrid reduction in time (MGRiT) are two of the most popular parallel-in-time methods. Both can be posed as preconditioned fixed-point iterations, for which convergence in an appropriate norm is defined by the (discrete) error- and residual-propagation operators. Here, we introduce a linear-algebra analysis for convergence of Parareal and two-level MGRiT, measuring the norm of error- and residual-propagation. The analysis is based on a “temporal approximation property” (TAP), which provides a measurement of how the coarse-grid time stepper approximates the fine-grid time stepper. For linear problems independent of time, satisfying the TAP provides necessary and sufficient conditions for two-grid convergence. Furthermore, these conditions are asymptotically exact, that is, the accuracy of the TAP defines the norm of error- and residual-propagation in the limit of a large number of time steps, N. For diagonalizable operators, explicit upper and lower bounds on convergence based on N can also be derived, confirming the asymptotic results are tight in practice.
We emphasize that for linear problems, the TAP defines exactly what is necessary of the coarse- and fine-grid time steppers for convergence of Paraeal and two-level MGRiT. Theory is demonstrated on two hyperbolic examples, the wave equation and advection-reaction equation, and is also used to prove which Runge-Kutta schemes yield convergence independent of spatial and temporal grid sizes for SPD spatial operators. We conclude by commenting on ongoing extensions of the theory to the linear time-dependent setting, which appears to follow a natural generalization by appealing to recent developments in generalized locally Toeplitz sequences.