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.
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.
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