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

DOI10.1137/18M1226208zbMATH Open1420.65039arXiv1810.07292OpenAlexW2964224480WikidataQ127903660 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)

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.

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

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

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)

Cites Work

• A note on parallel preconditioning for all-at-once evolutionary PDEs
• Two-Level Convergence Theory for Multigrid Reduction in Time (MGRIT)
• A ``parareal in time discretization of PDE's
• Nonlinear Convergence Analysis for the Parareal Algorithm
• Title not available (Why is that?)
• Asymptotic Results on the Spectra of Block Toeplitz Preconditioned Matrices
• Spectral and computational analysis of block Toeplitz matrices having nonnegative definite matrix-valued generating functions
• Extreme singular values and eigenvalues of non-Hermitian block Toeplitz matrices
• A Multigrid Tutorial, Second Edition
• Singular values and eigenvalues of non-Hermitian block Toeplitz matrices
• On the extreme eigenvalues of Hermitian (block) Toeplitz matrices
• Toward an efficient parallel in time method for partial differential equations
• On the Convergence and the Stability of the Parareal Algorithm to Solve Partial Differential Equations
• Analysis of the Parareal Time‐Parallel Time‐Integration Method
• A Space-Time Multigrid Method for Parabolic Partial Differential Equations
• Parallel Time Integration with Multigrid
• EXPLICIT EIGENVALUES AND INVERSES OF TRIDIAGONAL TOEPLITZ MATRICES WITH FOUR PERTURBED CORNERS
• Computing the generalized singular values/vectors of large sparse or structured matrix pairs
• Quasi-multiplication and \({}^*\)-algebras
• Asymptotic Spectra of Hermitian Block Toeplitz Matrices and Preconditioning Results
• Title not available (Why is that?)
• Convergence analysis of some second-order parareal algorithms
• On Generalizing the Algebraic Multigrid Framework
• A generalized predictive analysis tool for multigrid methods
• Preconditioning and Iterative Solution of All-at-Once Systems for Evolutionary Partial Differential Equations
• A note on MGR methods
• Scalar, Vector, and Matrix Mathematics
• Adaptive reduction-based AMG
• Multigrid methods with space-time concurrency
• Convergence Analysis for Three Parareal Solvers
• Wave propagation characteristics of Parareal
• Title not available (Why is that?)
• Multilevel Convergence Analysis of Multigrid-Reduction-in-Time
• Nonsymmetric Reduction-Based Algebraic Multigrid
• Parallel-In-Time Multigrid with Adaptive Spatial Coarsening for The Linear Advection and Inviscid Burgers Equations
• Convergence of the multigrid reduction in time algorithm for the linear elasticity equations
• Nonsymmetric Algebraic Multigrid Based on Local Approximate Ideal Restriction ($\ell$AIR)
• Multigrid interpretations of the parareal algorithm leading to an overlapping variant and MGRIT
• On the Ideal Interpolation Operator in Algebraic Multigrid Methods

Cited In (23)

• Fast Multigrid Reduction-in-Time for Advection via Modified Semi-Lagrangian Coarse-Grid Operators
• Robust Schur complement preconditioner for block-Toeplitz system and its application in image restoration
• A Uniform Spectral Analysis for a Preconditioned All-at-Once System from First-Order and Second-Order Evolutionary Problems
• Applications of time parallelization
• Time-periodic steady-state solution of fluid-structure interaction and cardiac flow problems through multigrid-reduction-in-time
• 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
• Multilevel parareal algorithm with averaging for oscillatory problems
• Tight Two-Level Convergence of Linear Parareal and MGRIT: Extensions and Implications in Practice
• Coarse-grid operator optimization in multigrid reduction in time for time-dependent Stokes and Oseen problems
• Constrained local approximate ideal restriction for advection-diffusion problems
• Convergence analysis of the parareal algorithm with nonuniform fine time grid
• A Unified Analysis Framework for Iterative Parallel-in-Time Algorithms
• IMEX Runge-Kutta Parareal for Non-diffusive Equations
• Fourier analysis of a time-simultaneous two-grid algorithm using a damped Jacobi waveform relaxation smoother for the one-dimensional heat equation
• The study of parareal algorithm for the linear switched systems
• Analysis of the parareal approach based on discontinuous Galerkin method for time‐dependent Stokes equations
• Rigorous convergence proof of space-time multigrid with coarsening in space
• Asynchronous Truncated Multigrid-Reduction-in-Time
• A class of analytic solutions for verification and convergence analysis of linear and nonlinear fluid-structure interaction algorithms
• Multilevel Convergence Analysis of 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

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)