Multilevel convergence analysis of multigrid-reduction-in-time
From MaRDI portal
Publication:5221031
DOI10.1137/19M1238812zbMATH Open1432.65177arXiv1812.11508OpenAlexW3010710024MaRDI QIDQ5221031FDOQ5221031
Authors: Andreas Hessenthaler, Ben S. Southworth, David A. Nordsletten, Oliver Röhrle, Jacob B. Schroder, Robert D. Falgout 
Publication date: 27 March 2020
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1812.11508
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.
a priori estimatesmultigridparallel-in-timemultigrid-reduction-in-time (MGRIT)analytic upper boundsmultilevel convergence theory
Parallel numerical computation (65Y05) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations (65L06) Finite difference methods for boundary value problems involving PDEs (65N06)
Cites Work
- Title not available (Why is that?)
- Two-level convergence theory for multigrid reduction in time (MGRIT)
- A ``parareal in time discretization of PDE's
- Solving Ordinary Differential Equations I
- Nonlinear Convergence Analysis for the Parareal Algorithm
- Time-decomposed parallel time-integrators: theory and feasibility studies for fluid, structure, and fluid-structure applications
- Title not available (Why is that?)
- Survey of the stability of linear finite difference equations
- Estimating the matrix \(p\)-norm
- 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
- A Space-Time Multigrid Method for Parabolic Partial Differential Equations
- 50 years of time parallel time integration
- Parallel time integration with multigrid
- Contractivity of Runge-Kutta methods
- Multi-grid dynamic iteration for parabolic equations
- Parallel high-order integrators
- Integrating an \(N\)-body problem with SDC and PFASST
- Parallel methods for integrating ordinary differential equations
- Multigrid methods. Proceedings of the Conference Held at Köln-Porz, November 23-27, 1981
- A multi-level spectral deferred correction method
- A generalized predictive analysis tool for multigrid methods.
- A user-friendly hybrid sparse matrix class in C++
- Title not available (Why is that?)
- Wave propagation characteristics of Parareal
- 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
- Parallel-in-time multigrid with adaptive spatial coarsening for the linear advection and inviscid Burgers equations
- Convergence analysis for parallel-in-time solution of hyperbolic systems.
- Multi-level spectral deferred corrections scheme for the shallow water equations on the rotating sphere
- Convergence of the multigrid reduction in time algorithm for the linear elasticity equations.
- Optimizing multigrid reduction‐in‐time and Parareal coarse‐grid operators for linear advection
- Tight two-level convergence of linear parareal and MGRIT: extensions and implications in practice
- A non-intrusive parallel-in-time adjoint solver with the xbraid library
- Multigrid interpretations of the parareal algorithm leading to an overlapping variant and MGRIT
- A root-node-based algebraic multigrid method
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
- Applications of time parallelization
- Time-periodic steady-state solution of fluid-structure interaction and cardiac flow problems through multigrid-reduction-in-time
- Necessary conditions and tight two-level convergence bounds for parareal and multigrid reduction in time
- 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
- A multigrid-reduction-in-time solver with a new two-level convergence for unsteady fractional Laplacian problems
- 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)
Uses Software
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)
