Multigrid interpretations of the parareal algorithm leading to an overlapping variant and MGRIT

Martin J. Gander, Felix Kwok, Hui Zhang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

20 Citations (Scopus)


The parareal algorithm is by construction a two level method, and there are several ways to interpret the parareal algorithm to obtain multilevel versions. We first review the three main interpretations of the parareal algorithm as a two-level method, a direct one, one based on geometric multigrid and one based on algebraic multigrid. The algebraic multigrid interpretation leads to the MGRIT algorithm, when using instead of only an F-smoother, a so called FCF-smoother. We show that this can be interpreted at the level of the parareal algorithm as generous overlap in time. This allows us to generalize the method to even larger overlap, corresponding in MGRIT to F(CF) ν-smoothing, ν≥ 1 , and we prove two new convergence results for such algorithms in the fully non-linear setting: convergence in a finite number of steps, becoming smaller when ν increases, and a general superlinear convergence estimate for this generalized version of MGRIT. We illustrate our results with numerical experiments, both for linear and non-linear systems of ordinary and partial differential equations. Our results show that overlap only sometimes leads to faster algorithms.

Original languageEnglish
Pages (from-to)59-74
Number of pages16
JournalComputing and Visualization in Science
Issue number3-4
Publication statusPublished - 1 Jul 2018
Externally publishedYes


  • Geometric and algebraic multigrid in time
  • Parareal algorithm with overlap

Cite this