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

Martin J. Gander, Wing Hong Felix Kwok, Hui Zhang*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

22 Citations (Scopus)

Abstract

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
Volume19
Issue number3-4
Early online date29 Jun 2018
DOIs
Publication statusPublished - Jul 2018

Scopus Subject Areas

  • Theoretical Computer Science
  • Software
  • Modelling and Simulation
  • Engineering(all)
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics

User-Defined Keywords

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

Fingerprint

Dive into the research topics of 'Multigrid interpretations of the parareal algorithm leading to an overlapping variant and MGRIT'. Together they form a unique fingerprint.

Cite this