Optimizing multigrid reduction-in-time (MGRIT) and Parareal coarse-grid operators for linear advection

Abstract

Parallel-in-time methods, such as multigrid reduction-in-time (MGRIT) and Parareal, provide an attractive option for increasing concurrency when simulating time-dependent PDEs in modern high-performance computing environments. While these techniques have been very successful for parabolic equations, it has often been observed that their performance suffers dramatically when applied to advection-dominated problems or purely hyperbolic PDEs using standard rediscretization approaches on coarse grids. In this paper, we apply MGRIT or Parareal to the constant-coefficient linear advection equation, appealing to existing convergence theory to provide insight into the typically non-scalable or even divergent behavior of these solvers for this problem. To overcome these failings, we replace rediscretization on coarse grids with improved coarse-grid operators that are computed by applying optimization techniques to approximately minimize error estimates from the convergence theory. One of our main findings is that, in order to obtain fast convergence as for parabolic problems, coarse-grid operators should take into account the behavior of the hyperbolic problem by tracking the characteristic curves. Our approach is tested for schemes of various orders using explicit or implicit Runge-Kutta methods combined with upwind-finite-difference spatial discretizations. In all cases, we obtain scalable convergence in just a handful of iterations, with parallel tests also showing significant speed-ups over sequential time-stepping. Our insight of tracking characteristics on coarse grids provides a key idea for solving the long-standing problem of efficient parallel-in-time integration for hyperbolic PDEs.

Some rewriting compared to V-2. This version has been accepted for publication in Numerical Linear Algebra with Applications

References in corpus (2)

• Explicit Parallel-in-time Integration of a Linear Acoustic-Advection System
• Wave propagation characteristics of Parareal

Cited by in corpus (9)

• Multigrid reduction-in-time convergence for advection problems: A Fourier analysis perspective
• Constrained Local Approximate Ideal Restriction for Advection-Diffusion Problems
• PyMGRIT: A Python Package for the parallel-in-time method MGRIT
• asQ: parallel-in-time finite element simulations using ParaDiag for geoscientific models and beyond
• AIR algebraic multigrid for a space-time hybridizable discontinuous Galerkin discretization of advection(-diffusion)
• Tuning Multigrid Methods with Robust Optimization
• Impact of spatial coarsening on Parareal convergence for the linear advection equation
• Parallel-in-time integration of the shallow water equations on the rotating sphere using Parareal and MGRIT
• Parallel-in-time solution of scalar nonlinear conservation laws