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

DOI10.1137/18M1226208zbMATH Open1420.65039OpenAlexW2964224480WikidataQ127903660 ScholiaQ127903660MaRDI QIDQ5232109FDOQ5232109

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

convergencemultigridreductionparallel-in-timepararealMGRiT

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Toeplitz, Cauchy, and related matrices (15B05) 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

• 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?)
• A Multigrid Tutorial, Second Edition
• 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 note on MGR methods
• A note on parallel preconditioning for all-at-once evolutionary PDEs
• 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
• 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 (\(\ell\)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 Ideal Interpolation Operator in Algebraic Multigrid Methods
• On the extreme eigenvalues of Hermitian (block) Toeplitz matrices
• 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

(26)

• Convergence analysis of the parareal algorithm with nonuniform fine time grid
• Multilevel convergence analysis of multigrid-reduction-in-time
• The study of parareal algorithm for the linear switched systems
• Fast Multigrid Reduction-in-Time for Advection via Modified Semi-Lagrangian Coarse-Grid Operators
• Analysis of the parareal approach based on discontinuous Galerkin method for time‐dependent Stokes equations
• Weighted relaxation for multigrid reduction in time
• Convergence of the multigrid reduction in time algorithm for the linear elasticity equations.
• Robust Schur complement preconditioner for block-Toeplitz system and its application in image restoration
• IMEX Runge-Kutta parareal for non-diffusive equations
• Applications of time parallelization
• A uniform spectral analysis for a preconditioned all-at-once system from first-order and second-order evolutionary problems
• Coarse-grid operator optimization in multigrid reduction in time for time-dependent Stokes and Oseen problems
• Time-periodic steady-state solution of fluid-structure interaction and cardiac flow problems through multigrid-reduction-in-time
• Constrained local approximate ideal restriction for advection-diffusion problems
• Multigrid Reduction in Time for Nonlinear Parabolic Problems: A Case Study
• Asynchronous Truncated Multigrid-Reduction-in-Time
• Multilevel parareal algorithm with averaging for oscillatory problems
• Two-level convergence theory for multigrid reduction in time (MGRIT)
• A class of analytic solutions for verification and convergence analysis of linear and nonlinear fluid-structure interaction algorithms
• A multigrid-reduction-in-time solver with a new two-level convergence for unsteady fractional Laplacian problems
• 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
• 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
• Interpretation of parareal as a two-level additive Schwarz in time preconditioner and its acceleration with GMRES
• Exponential Runge-Kutta parareal for non-diffusive equations

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)