NECESSARY CONDITIONS AND TIGHT TWO-LEVEL CONVERGENCE BOUNDS FOR PARAREAL AND MULTIGRID REDUCTION IN TIME

Parareal and multigrid reduction in time (MGRiT) are two of the most popular parallel-in-time methods. The basic idea is to treat time integration in a parallel context by using a multigrid method in time. If Phi is the (fine-grid) time-stepping scheme of interest, such as any Runge-Kutta scheme, then let psi denote a coarse-grid time-stepping scheme chosen to approximate k steps of Phi, where k >= 1. In particular, Psi defines the coarse-grid correction, and evaluating Psi should be (significantly) cheaper than evaluating Phi(k). Parareal is a two-level method with a fixed relaxation scheme, and MGRiT is a generalization to the multilevel setting, with the additional option of a modified, stronger relaxation scheme. A number of papers have studied the convergence of Parareal and MGRiT. However, general conditions on the convergence of Parareal or MGRiT that answer the following simple questions have yet to be developed: (i) For a given Phi and k, what is the best Psi? (ii) Can Parareal/MGRiT converge for my problem? This work derives necessary and sufficient conditions for the convergence of Parareal and MGRiT applied to linear problems, along with tight two-level convergence bounds, under minimal additional assumptions on Phi and Psi. Results all rest on the introduction of a temporal approximation property (TAP) that indicates how Phi(k) must approximate the action of Psi on different vectors. Loosely, for unitarily diagonalizable operators, the TAP indicates that the fine-grid and coarse-grid time integration schemes must integrate geometrically smooth spatial components similarly, and less so for geometrically high frequency. In the (nonunitarily) diagonalizable setting, the conditioning of each eigenvector, v(i), must also be reflected in how well Psi v(i) similar to Phi(k)v(i). In general, worst-case convergence bounds are exactly given by min phi < 1 such that an inequality along the lines of parallel to(Psi - Phi(k))v parallel to <= phi parallel to(I - Psi)v parallel to holds for all v. Such inequalities are formalized as different realizations of the TAP in section 2 and form the basis for convergence of MGRiT and Parareal applied to linear problems.