Two-Level Convergence Theory for Multigrid Reduction in Time (MGRIT)
Authors:
- V. A. DobrevVDV. A. Dobrev
- Tz. KolevTKTz. Kolev
- N. A. PeterssonNPN. A. Petersson
- J. B. SchroderJSJ. B. Schroder
- 1 January 2017
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 39 (5) , S501-S527
Abstract
In this paper we develop a two-grid convergence theory for the parallel-in-time scheme known as multigrid reduction in time (MGRIT), as it is implemented in the open-source package [ XBraid: Parallel Multigrid in Time, http://llnl.gov/casc/xbraid]. MGRIT is a scalable and multilevel approach to parallel-in-time simulations that nonintrusively uses existing time-stepping schemes, and in a specific two-level setting it is equivalent to the widely known parareal algorithm. The goal of this paper is twofold. First, we present a two-level MGRIT convergence analysis for linear problems where the spatial discretization matrix can be diagonalized, and then apply this analysis to our two basic model problems, the heat equation and the advection equation. One important assumption is that the coarse and fine time-grid propagators can be diagaonalized by the same set of eigenvectors, which is often the case when the same spatial discretization operator is used on the coarse and fine time grids. In many cases, the MGRIT algorithm is guaranteed to converge, and we demonstrate numerically that the theoretically predicted convergence rates are sharp in practice for our model problems. Second, we explore how the convergence of MGRIT compares to the stability of the chosen time-stepping scheme. In particular, we demonstrate that a stable time-stepping scheme does not necessarily imply convergence of MGRIT, although MGRIT with FCF-relaxation always converges for the diffusion dominated problems considered here.Keywords
Funding Information
- Lawrence Livermore National Laboratory (DE-AC52-07NA27344, LLNL-JRNL-692418)
This publication has 18 references indexed in Scilit:
- A generalized predictive analysis tool for multigrid methodsNumerical Linear Algebra with Applications, 2015
- Parallel Time Integration with MultigridSIAM Journal on Scientific Computing, 2014
- Stable Parareal in Time Method for First- and Second-Order Hyperbolic SystemsSIAM Journal on Scientific Computing, 2013
- Toward an efficient parallel in time method for partial differential equationsCommunications in Applied Mathematics and Computational Science, 2012
- A hybrid parareal spectral deferred corrections methodCommunications in Applied Mathematics and Computational Science, 2010
- Analysis of the Parareal Time‐Parallel Time‐Integration MethodSIAM Journal on Scientific Computing, 2007
- Numerical Conservation Properties of H(div)-Conforming Least-Squares Finite Element Methods for the Burgers EquationSIAM Journal on Scientific Computing, 2005
- Résolution d'EDP par un schéma en temps «pararéel »Comptes Rendus de l'Académie des Sciences - Series I - Mathematics, 2001
- A Space-Time Multigrid Method for Parabolic Partial Differential EquationsSIAM Journal on Scientific Computing, 1995
- Parallel methods for integrating ordinary differential equationsCommunications of the ACM, 1964