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
- 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?)
- 50 years of time parallel time integration
- A Space-Time Multigrid Method for Parabolic Partial Differential Equations
- 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 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
- 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 Reduction in Time for Nonlinear Parabolic Problems: A Case Study
- 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
- 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
(17)- Efficient multigrid reduction-in-time for method-of-lines discretizations of linear advection
- Time domain decomposition of parabolic control problems based on discontinuous Galerkin semi-discretization
- Time-periodic steady-state solution of fluid-structure interaction and cardiac flow problems through multigrid-reduction-in-time
- Applications of time parallelization
- Necessary conditions and tight two-level convergence bounds for parareal and multigrid reduction in time
- A multigrid-reduction-in-time solver with a new two-level convergence for unsteady fractional Laplacian problems
- Enhancing the convergence of the multigrid-reduction-in-time method for the Euler and Navier-Stokes equations
- Multigrid Reduction in Time for Nonlinear Parabolic Problems: A Case Study
- Weighted relaxation for multigrid reduction in time
- Multilevel parareal algorithm with averaging for oscillatory problems
- Multigrid reduction in time with Richardson extrapolation
- A Unified Analysis Framework for Iterative Parallel-in-Time Algorithms
- Fourier analysis of a time-simultaneous two-grid algorithm using a damped Jacobi waveform relaxation smoother for the one-dimensional heat equation
- Rigorous convergence proof of space-time multigrid with coarsening in space
- Tight two-level convergence of linear parareal and MGRIT: extensions and implications in practice
- Convergence Acceleration for Time-Dependent Parametric Multifidelity Models
- Two-level convergence theory for multigrid reduction in time (MGRIT)
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)
