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

Hans De Sterck, Robert D. Falgout, Stephanie Friedhoff, Oliver A. Krzysik, Scott P. MacLachlan

Abstract

Parallel-in-time (PinT) methods, such as Multigrid Reduction-in-Time (MGRIT) and Parareal, have historically struggled with advection-dominated hyperbolic problems. Standard coarse-grid operators often lead to slow convergence or divergence because they fail to accurately propagate wave-like information. This paper introduces a novel optimization-based framework for designing coarse-grid operators. By formulating the operator design as a linear least squares problem that prioritizes spectral matching for smooth modes and incorporates characteristic tracking, the authors demonstrate robust, scalable convergence. Numerical results show up to 18x speedup over sequential time-stepping for high-order discretizations on large-scale parallel systems.

Introduction

The shift toward massive parallelization in high-performance computing necessitates algorithms that can parallelize across the temporal dimension. While MGRIT and Parareal are highly effective for parabolic (diffusion) equations, their application to hyperbolic (advection) problems has been a significant challenge. In these cases, the coarse-grid operator often fails to capture the physical propagation of information, leading to solver inefficiencies that can make parallel execution slower than traditional sequential time-stepping.

Optimization-Based Coarse Grid Design

The authors propose a departure from standard rediscretization. Instead, they treat the coarse-grid operator ($\Psi$) as an optimization target. The goal is to find a sparse operator that minimizes the difference between the actual coarse-grid propagation and the "ideal" propagation derived from the fine-grid operator over multiple steps.

A critical component of this approach is characteristic tracking. For a wave moving at a specific velocity, the spatial stencil of the coarse operator must be shifted to account for the distance traveled during the larger coarse time step. Furthermore, the optimization uses a weighted least squares approach to prioritize "smooth" spatial modes, which are the most difficult to resolve in hyperbolic problems.

Spectral matching of eigenvalues and the resulting error bound for smooth modes.

As shown in Figure 5, the optimization successfully aligns the eigenvalues of the coarse operator ($\mu_k$) with the ideal eigenvalues ($\lambda_k^2$) for low frequencies ($\theta_k \approx 0$). This spectral matching is essential for ensuring that the MGRIT/Parareal iterations converge rapidly.

Performance and Scalability

The methodology was tested using a variety of spatial discretizations, ranging from 1st-order to 5th-order upwind schemes, and both explicit (ERK) and implicit (SDIRK) Runge-Kutta time-stepping methods.

Convergence of discretization error for various ERK and SDIRK schemes as the grid is refined.

Figure 3 demonstrates that the optimized PinT solvers maintain the expected high-order convergence rates for both explicit and implicit schemes. More importantly, the iteration counts remained nearly constant as the problem size increased, indicating excellent algorithmic scalability. In practical tests on the Quartz supercomputer using the XBraid library, the authors achieved speedups of 13.7x to 18.1x using 1024 processors compared to sequential methods.

Conclusion

By shifting the focus from simple rediscretization to a targeted optimization problem that respects physical characteristics, this work overcomes a major hurdle in parallel-in-time integration. The principle of characteristic tracking provides a clear path forward for extending these methods to more complex, non-linear hyperbolic systems in higher dimensions.

Summary updated

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.
BibTeX
@article{sterck2021optimizing,
  author = {Hans De Sterck and Robert D. Falgout and Stephanie Friedhoff and Oliver A. Krzysik and Scott P. MacLachlan},
  title = {{Optimizing multigrid reduction-in-time and Parareal coarse-grid operators for linear advection}},
  journal = {Numer. Linear Algebra Appl},
  year = {2021},
  doi = {10.1002/nla.2367},
}
Figure