Multilevel convergence analysis of multigrid-reduction-in-time
From MaRDI portal
Publication:5221031
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.
Recommendations
- Two-level convergence theory for multigrid reduction in time (MGRIT)
- Necessary conditions and tight two-level convergence bounds for parareal and multigrid reduction in time
- Tight two-level convergence of linear parareal and MGRIT: extensions and implications in practice
- Parallel time integration with multigrid
- Convergence of the multigrid reduction in time algorithm for the linear elasticity equations.
Cites work
- 50 years of time parallel time integration
- A ``parareal in time discretization of PDE's
- A generalized predictive analysis tool for multigrid methods.
- A multi-level spectral deferred correction method
- A non-intrusive parallel-in-time adjoint solver with the xbraid library
- A root-node-based algebraic multigrid method
- A Space-Time Multigrid Method for Parabolic Partial Differential Equations
- A user-friendly hybrid sparse matrix class in C++
- Contractivity of Runge-Kutta methods
- Convergence analysis for parallel-in-time solution of hyperbolic systems.
- Convergence of the multigrid reduction in time algorithm for the linear elasticity equations.
- Estimating the matrix p-norm
- scientific article; zbMATH DE number 940566 (Why is no real title available?)
- scientific article; zbMATH DE number 775681 (Why is no real title available?)
- scientific article; zbMATH DE number 5180707 (Why is no real title available?)
- Integrating an N-body problem with SDC and PFASST
- Multi-grid dynamic iteration for parabolic equations
- Multi-level spectral deferred corrections scheme for the shallow water equations on the rotating sphere
- Multigrid interpretations of the parareal algorithm leading to an overlapping variant and MGRIT
- Multigrid methods. Proceedings of the Conference Held at Köln-Porz, November 23-27, 1981
- Multigrid Reduction in Time for Nonlinear Parabolic Problems: A Case Study
- Necessary conditions and tight two-level convergence bounds for parareal and multigrid reduction in time
- Nonlinear Convergence Analysis for the Parareal Algorithm
- Optimizing multigrid reduction‐in‐time and Parareal coarse‐grid operators for linear advection
- Parallel high-order integrators
- Parallel methods for integrating ordinary differential equations
- Parallel time integration with multigrid
- Parallel-in-time multigrid with adaptive spatial coarsening for the linear advection and inviscid Burgers equations
- Solving Ordinary Differential Equations I
- Survey of the stability of linear finite difference equations
- Tight two-level convergence of linear parareal and MGRIT: extensions and implications in practice
- Time-decomposed parallel time-integrators: theory and feasibility studies for fluid, structure, and fluid-structure applications
- Time-parallel implicit integrators for the near-real-time prediction of linear structural dynamic responses
- Toward an efficient parallel in time method for partial differential equations
- Two-level convergence theory for multigrid reduction in time (MGRIT)
- Wave propagation characteristics of Parareal
Cited in
(21)- A multigrid-reduction-in-time solver with a new two-level convergence for unsteady fractional Laplacian problems
- Multigrid reduction in time with Richardson extrapolation
- Rigorous convergence proof of space-time multigrid with coarsening in space
- Time-periodic steady-state solution of fluid-structure interaction and cardiac flow problems through multigrid-reduction-in-time
- Time domain decomposition of parabolic control problems based on discontinuous Galerkin semi-discretization
- Fourier analysis of a time-simultaneous two-grid algorithm using a damped Jacobi waveform relaxation smoother for the one-dimensional heat equation
- On “Optimal” h‐independent convergence of Parareal and multigrid‐reduction‐in‐time using Runge‐Kutta time integration
- Tight two-level convergence of linear parareal and MGRIT: extensions and implications in practice
- Necessary conditions and tight two-level convergence bounds for parareal and multigrid reduction in time
- Convergence Acceleration for Time-Dependent Parametric Multifidelity Models
- Multigrid Reduction in Time for Nonlinear Parabolic Problems: A Case Study
- Two-level convergence theory for multigrid reduction in time (MGRIT)
- Weighted relaxation for multigrid reduction in time
- A Unified Analysis Framework for Iterative Parallel-in-Time Algorithms
- Efficient multigrid reduction-in-time for method-of-lines discretizations of linear advection
- Applications of time parallelization
- Enhancing the convergence of the multigrid-reduction-in-time method for the Euler and Navier-Stokes equations
- Multilevel parareal algorithm with averaging for oscillatory problems
- TorchBraid: high-performance layer-parallel training of deep neural networks with MPI and GPU acceleration
- Time parallelization for hyperbolic and parabolic problems
- The symmetric V-cycle can diverge under the multigrid axioms for cell-centred discretisations
This page was built for publication: Multilevel convergence analysis of multigrid-reduction-in-time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5221031)
