Multilevel convergence analysis of multigrid-reduction-in-time
Authors:
- Andreas HessenthalerAHAndreas Hessenthaler
- Oliver RöhrleOROliver Röhrle
- Robert D. FalgoutRFRobert D. Falgout
- Jacob B. SchroderJSJacob B. Schroder
Preprint
Abstract
This paper presents a multilevel convergence framework for multigrid-reduction-in-time (MGRIT) as a generalization of previous two-grid estimates. The framework provides a priori upper bounds on the convergence of MGRIT V- and F-cycles, with different relaxation schemes, by deriving the respective residual and error propagation operators. The residual and error operators are functions of the time stepping operator, analyzed directly and bounded in norm, both numerically and analytically. We present various upper bounds of different computational cost and varying sharpness. These upper bounds are complemented by proposing analytic formulae for the approximate convergence factor of V-cycle algorithms that take the number of fine grid time points, the temporal coarsening factors, and the eigenvalues of the time stepping operator as parameters. The paper concludes with supporting numerical investigations of parabolic (anisotropic diffusion) and hyperbolic (wave equation) model problems. We assess the sharpness of the bounds and the quality of the approximate convergence factors. Observations from these numerical investigations demonstrate the value of the proposed multilevel convergence framework for estimating MGRIT convergence a priori and for the design of a convergent algorithm. We further highlight that observations in the literature are captured by the theory, including that two-level Parareal and multilevel MGRIT with F-relaxation do not yield scalable algorithms and the benefit of a stronger relaxation scheme. An important observation is that with increasing numbers of levels MGRIT convergence deteriorates for the hyperbolic model problem, while constant convergence factors can be achieved for the diffusion equation. The theory also indicates that L-stable Runge-Kutta schemes are more amendable to multilevel parallel-in-time integration with MGRIT than A-stable Runge-Kutta schemes.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Tight Two-Level Convergence of Linear Parareal and MGRIT: Extensions and Implications in Practice2021
- A parallel-in-time algorithm for variable step multistep methodsJournal of Computational Science, 2019
- Multi-level spectral deferred corrections scheme for the shallow water equations on the rotating sphereJournal of Computational Physics, 2019
- Convergence of the multigrid reduction in time algorithm for the linear elasticity equationsNumerical Linear Algebra with Applications, 2018
- A generalized predictive analysis tool for multigrid methodsNumerical Linear Algebra with Applications, 2015
- A multi-level spectral deferred correction methodBIT Numerical Mathematics, 2014
- Time‐decomposed parallel time‐integrators: theory and feasibility studies for fluid, structure, and fluid–structure applicationsInternational Journal for Numerical Methods in Engineering, 2003
- A Space-Time Multigrid Method for Parabolic Partial Differential EquationsSIAM Journal on Scientific Computing, 1995
- Multi-grid dynamic iteration for parabolic equationsBIT Numerical Mathematics, 1987
- Survey of the stability of linear finite difference equationsCommunications on Pure and Applied Mathematics, 1956