Two-level convergence theory for multigrid reduction in time (MGRIT). 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,]. 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.

References in zbMATH (referenced in 15 articles , 1 standard article )

Showing results 1 to 15 of 15.
Sorted by year (citations)

  1. Falgout, R. D.; Manteuffel, T. A.; O’Neill, B.; Schroder, J. B.: Multigrid reduction in time with Richardson extrapolation (2021)
  2. Lin, Xue-lei; Ng, Michael: An all-At-once preconditioner for evolutionary partial differential equations (2021)
  3. Yue, Xiaoqiang; Pan, Kejia; Zhou, Jie; Weng, Zhifeng; Shu, Shi; Tang, Juan: A multigrid-reduction-in-time solver with a new two-level convergence for unsteady fractional Laplacian problems (2021)
  4. Gander, Martin J.; Kwok, Felix; Salomon, Julien: PARAOPT: a parareal algorithm for optimality systems (2020)
  5. Gander, Martin J.; Wu, Shu-Lin: A diagonalization-based parareal algorithm for dissipative and wave propagation problems (2020)
  6. Hessenthaler, Andreas; Balmus, Maximilian; Röhrle, Oliver; Nordsletten, David: A class of analytic solutions for verification and convergence analysis of linear and nonlinear fluid-structure interaction algorithms (2020)
  7. Hessenthaler, Andreas; Southworth, Ben S.; Nordsletten, David; Röhrle, Oliver; Falgout, Robert D.; Schroder, Jacob B.: Multilevel convergence analysis of multigrid-reduction-in-time (2020)
  8. Notay, Yvan: Analysis of two-grid methods: the nonnormal case (2020)
  9. Günther, Stefanie; Gauger, N. R.; Schroder, J. B.: A non-intrusive parallel-in-time approach for simultaneous optimization with unsteady PDEs (2019)
  10. Manteuffel, Thomas A.; MüNzenmaier, Steffen; Ruge, John; Southworth, Ben: Nonsymmetric reduction-based algebraic multigrid (2019)
  11. Southworth, Ben S.: Necessary conditions and tight two-level convergence bounds for parareal and multigrid reduction in time (2019)
  12. Wu, Shu-Lin; Zhou, Tao: Acceleration of the two-level MGRIT algorithm via the diagonalization technique (2019)
  13. Yue, Xiaoqiang; Shu, Shi; Xu, Xiaowen; Bu, Weiping; Pan, Kejia: Parallel-in-time multigrid for space-time finite element approximations of two-dimensional space-fractional diffusion equations (2019)
  14. Wu, Shu-Lin: Toward parallel coarse grid correction for the parareal algorithm (2018)
  15. Dobrev, V. A.; Kolev, Tz.; Petersson, N. A.; Schroder, J. B.: Two-level convergence theory for multigrid reduction in time (MGRIT) (2017)