Necessary conditions and tight two-level convergence bounds for parareal and multigrid reduction in time

DOI10.1137/18M1226208MaRDI QIDQ5232109zbMATH OpenOpenAlexWikidataFDO

Authors Ben S. Southworth

Publication date 29 August 2019

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.07292

zbMATH Keywords

convergenceMGRiTmultigridparallel-in-timepararealreduction

Mathematics Subject Classification ID

Toeplitz, Cauchy, and related matrices (15B05) Iterative numerical methods for linear systems (65F10) Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs (65M12) Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs (65M55)

Abstract: Parareal and multigrid reduction in time (MGRiT) are two of the most popular parallel-in-time methods. The idea is to treat time integration in a parallel context by using a multigrid method in time. If $Phi$ is a (fine-grid) time-stepping scheme, let $Psi$ denote a "coarse-grid" time-stepping scheme chosen to approximate $k$ steps of $Phi$, $kgeq1$. In particular, $Psi$ defines the coarse-grid correction, and evaluating $Psi$ should be (significantly) cheaper than evaluating $Ph{i}^k$. A number of papers have studied the convergence of Parareal and MGRiT. However, there have yet to be general conditions developed on the convergence of Parareal or MGRiT that answer simple questions such as, (i) for a given $Phi$ and $k$, what is the best $Psi$, or (ii) can Parareal/MGRiT converge for my problem? This work derives necessary and sufficient conditions for the convergence of Parareal and MGRiT applied to linear problems, along with tight two-level convergence bounds. Results rest on the introduction of a "temporal approximation property" (TAP) that indicates how $Ph{i}^k$ must approximate the action of $Psi$ on different vectors. Loosely, for unitarily diagonalizable operators, the TAP indicates that fine-grid and coarse-grid time integration schemes must integrate geometrically smooth spatial components similarly, and less so for geometrically high frequency. In the (non-unitarily) diagonalizable setting, the conditioning of each eigenvector, $mathbf{v}_i$, must also be reflected in how well $Psimathbf{v}_{i}simPh{i}^{k}mathbf{v}_i$. In general, worst-case convergence bounds are exactly given by $minvarphi<1$ such that an inequality along the lines of $|(Psi-Ph{i}^k)mathbfv|leqvarphi|(I-Psi)mathbfv|$ holds for all $mathbfv$. Such inequalities are formalized as different realizations of the TAP, and form the basis for convergence of MGRiT and Parareal.

Recommendations

• Tight two-level convergence of linear parareal and MGRIT: extensions and implications in practice
• Two-level convergence theory for multigrid reduction in time (MGRIT)
• Multilevel convergence analysis of multigrid-reduction-in-time
• Parallel time integration with multigrid
• Interpretation of parareal as a two-level additive Schwarz in time preconditioner and its acceleration with GMRES

Cites work

• A ``parareal in time discretization of PDE's
• A generalized predictive analysis tool for multigrid methods.
• A Multigrid Tutorial, Second Edition
• A note on MGR methods
• A note on parallel preconditioning for all-at-once evolutionary PDEs
• A Space-Time Multigrid Method for Parabolic Partial Differential Equations
• Adaptive reduction-based AMG
• Analysis of the Parareal Time‐Parallel Time‐Integration Method
• Asymptotic Results on the Spectra of Block Toeplitz Preconditioned Matrices
• Asymptotic Spectra of Hermitian Block Toeplitz Matrices and Preconditioning Results
• Computing the generalized singular values/vectors of large sparse or structured matrix pairs
• Convergence analysis for three parareal solvers
• Convergence analysis of some second-order parareal algorithms
• Convergence of the multigrid reduction in time algorithm for the linear elasticity equations.
• EXPLICIT EIGENVALUES AND INVERSES OF TRIDIAGONAL TOEPLITZ MATRICES WITH FOUR PERTURBED CORNERS
• Extreme singular values and eigenvalues of non-Hermitian block Toeplitz matrices
• scientific article; zbMATH DE number 3124252 (Why is no real title available?)
• scientific article; zbMATH DE number 2143558 (Why is no real title available?)
• scientific article; zbMATH DE number 5180707 (Why is no real title available?)
• Multigrid interpretations of the parareal algorithm leading to an overlapping variant and MGRIT
• Multigrid methods with space-time concurrency
• Multilevel convergence analysis of multigrid-reduction-in-time
• Nonlinear Convergence Analysis for the Parareal Algorithm
• Nonsymmetric algebraic multigrid based on local approximate ideal restriction (AIR)
• Nonsymmetric reduction-based algebraic multigrid
• On Generalizing the Algebraic Multigrid Framework
• On the Convergence and the Stability of the Parareal Algorithm to Solve Partial Differential Equations
• On the extreme eigenvalues of Hermitian (block) Toeplitz matrices
• On the Ideal Interpolation Operator in Algebraic Multigrid Methods
• Parallel time integration with multigrid
• Parallel-in-time multigrid with adaptive spatial coarsening for the linear advection and inviscid Burgers equations
• Preconditioning and Iterative Solution of All-at-Once Systems for Evolutionary Partial Differential Equations
• Quasi-multiplication and \({}^*\)-algebras
• Scalar, Vector, and Matrix Mathematics
• Singular values and eigenvalues of non-Hermitian block Toeplitz matrices
• Spectral and computational analysis of block Toeplitz matrices having nonnegative definite matrix-valued generating functions
• 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

(31)

• A multigrid-reduction-in-time solver with a new two-level convergence for unsteady fractional Laplacian problems
• The study of parareal algorithm for the linear switched systems
• 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
• Robust Schur complement preconditioner for block-Toeplitz system and its application in image restoration
• A class of analytic solutions for verification and convergence analysis of linear and nonlinear fluid-structure interaction algorithms
• Fourier analysis of a time-simultaneous two-grid algorithm using a damped Jacobi waveform relaxation smoother for the one-dimensional heat equation
• Convergence of the multigrid reduction in time algorithm for the linear elasticity equations.
• 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
• IMEX Runge-Kutta parareal for non-diffusive equations
• A uniform spectral analysis for a preconditioned all-at-once system from first-order and second-order evolutionary problems
• Multilevel convergence analysis of multigrid-reduction-in-time
• 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
• Analysis of the parareal approach based on discontinuous Galerkin method for time‐dependent Stokes equations
• Asynchronous Truncated Multigrid-Reduction-in-Time
• Exponential Runge-Kutta parareal for non-diffusive equations
• Interpretation of parareal as a two-level additive Schwarz in time preconditioner and its acceleration with GMRES
• Applications of time parallelization
• Fast Multigrid Reduction-in-Time for Advection via Modified Semi-Lagrangian Coarse-Grid Operators
• Multilevel parareal algorithm with averaging for oscillatory problems
• Coarse-grid operator optimization in multigrid reduction in time for time-dependent Stokes and Oseen problems
• Convergence analysis of the parareal algorithm with nonuniform fine time grid
• Constrained local approximate ideal restriction for advection-diffusion problems
• TorchBraid: high-performance layer-parallel training of deep neural networks with MPI and GPU acceleration
• Parallel-in-time solution of scalar nonlinear conservation laws
• Robust convergence of parareal algorithms with arbitrarily high-order fine propagators
• Optimizing coarse propagators in parareal algorithms

Describes a project that uses

Uses Software

• pyParareal
• MGRIT
• PARALAAOMPI

This page was built for publication: Necessary conditions and tight two-level convergence bounds for parareal and multigrid reduction in time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232109)