Source-linked AI summary
Tolerance Proportionality and Computational Stability in Adaptive Parallel-in-Time Runge-Kutta Methods
Imre Fekete, Ferenc Izsák, Vendel P. Kupás, Gustaf Söderlind
TL;DR
The paper asks whether adaptive parallel-in-time integration can retain tolerance proportionality and computational stability. It tests modified MGRIT refinement and finds rmod improves stability while remaining comparable to sequential computation, with parallel runtime reduction observed in diffusion tests.
Problem
Can adaptive parallel integration retain tolerance proportionality and computational stability, which require errors to stay near the prescribed tolerance as it changes?
Source: §2.2 · p. 4Method
The authors test MGRIT refinement strategies, including a modified factor, with the Bogacki–Shampine method and XBraid on ODE problems.
Source: §3.2 · pp. 6, 8Results
rmod provides the best computational stability with performance comparable to sequential computation; diffusion tests also show good tolerance proportionality and expected parallel runtime reduction.
Source: §3.2.3 · p. 11, §3.3 · p. 11Takeaways & Limitations
Adjusting the refinement factor to rmod improves stability while preserving performance comparable to sequential computation in the reported tests.
Source: §3.2.3 · p. 11Current results provide satisfactory quality only for nonstiff or at most mildly stiff problems, though heuristics significantly improved the step-size sequence for a stiff van der Pol case.
Source: §4.2 · pp. 13–14
Abstract
from arXiv · showhide
In this paper, we investigate how adaptive time-integration strategies can be effectively combined with parallel-in-time numerical methods for solving systems of ordinary differential equations. Our focus is particularly on their influence on tolerance proportionality. We examine various grid-refinement strategies within the multigrid reduction-in-time (MGRIT) framework. Our results show that a simple adjustment to the original refinement factor can substantially improve computational stability and reliability. Through numerical experiments on standard test problems using the XBraid library, we demonstrate that parallel-in-time solutions closely match their sequential counterparts. Moreover, with the use of multiple processors, computing time can be significantly reduced.
1 Introduction
Adaptive time stepping addresses the fine resolution required near steep gradients, while parallel-in-time methods offer another route to accelerate ODE simulations. This paper examines tolerance proportionality and computational stability in adaptive MGRIT, and tests a modified refinement factor on ODE and PDE-derived problems.
1 Introduction
- Stiff ODEs can require very fine steps near steep gradients, and heuristic step selection can be unstable without smooth changes between successive step sizes.The motivation includes chemical reaction systems and large systems from PDE semi-discretization.Source: §1 · p. 1
- Adaptive parallel-in-time studies have focused on error and runtime metrics, leaving the response of global error to changes in the specified tolerance as another reliability question.For regular solutions, the paper describes tolerance proportionality as a proportionally small error change following a small tolerance change.Source: §1 · p. 2
- The paper modifies a step-size refinement factor within MGRIT and investigates tolerance proportionality and computational stability across classical ODE and PDE-derived test problems.The approach builds on a step-size selection strategy proposed in.Source: §1 · p. 2
2 Preliminaries: Main Tools and Requirements
This section introduces MGRIT and adaptive step-size control as tools for parallel-in-time integration, then sets out the error behavior and controller properties the method must address.
2.1 The MGRIT Algorithm
- MGRIT iteratively approximates the solution over the time domain, using parallel temporal computation and coarse-grid updates to improve the approximation.The two-grid method is equivalent to parareal; recursive coarsening yields V-, W-, and F-cycles, while XBraid provides the implementation used in the experiments.Source: §2.1 · pp. 2–4
- The MGRIT two-grid convergence rate depends on the accuracy of the coarse-grid propagator, and a grid that remains too fine can make the coarse solve computationally expensive.The algorithm has O(N) runtime; reported studies indicate that parallel resources can yield significant speedup even though a sequential one-step method can outperform it with few processors.Source: §2.1 · p. 3
2.2 Tolerance Proportionality and Computational Stability
- Tolerance proportionality requires global error to change in proportion to the prescribed tolerance, with the error remaining near tolerance rather than merely below it.For regular global error accumulation, the paper relates this property to computational stability.Source: §2.2 · p. 4
2.3 Classical Recursive Controllers
- In sequential adaptive integration, recursive controllers update step sizes using local-error control; smooth sequences may require changing the step size at every step.PI and PID controllers can use coefficients to improve stability and regularity, while controller design should match the method and problem class.Source: §2.3 · p. 5
3 Results
Across the ODE tests, the modified refinement factor rmod suppresses zigzags and improves tolerance proportionality; on diffusion tests, it is associated with good computational stability and reduced runtime under parallelization.
3 Results
- The refinement factor r is computed from the current step size and the error-estimator suggestion, assuming the step-size–error relation is in its asymptotic regime.The ceiling function ensures subintervals divide into an integer number of smaller subintervals.Source: §3 · p. 5
3.1 ODE Test Problems
- The ODE suite includes a linear two-compartment dilution process, Lotka–Volterra dynamics, and van der Pol dynamics that transition from nonstiff to stiff behavior as μ increases.The van der Pol nonstiff computation uses μ = 2.Source: §3.1 · p. 6
3.2 Results for Refinement Factors r, rmod, and rexp
- On three ODE tests, the original MGRIT refinement produced average tolerance scaling and close agreement with sequential step sizes at tol = 10^-11, but also zigzags.The ceiling function makes the refinement factor sensitive to small values, impairing pointwise tolerance proportionality and local-error equidistribution.Source: §3.2 · p. 6
3.2.1 The Final Algorithm with rmod
- The proposed rmod refinement largely suppresses zigzags and yields smoother step-size sequences with improved tolerance proportionality.The tests begin on a uniform temporal grid and use three V-cycles between consecutive refinements.Source: §3.2.1 · p. 8
3.2.2 An Attempt with Exponential-Forgetting Filters
- The alternative rexp reduces the integral gain from 1 to 2/3, but does not produce smoother step-size sequences; the ceiling function appears to explain this difference.The corresponding figures are available in the cited repository.Source: §3.2.2 · p. 9
3.2.3 Tolerance Proportionality for the Algorithm (A1)–(A5)
- rmod smooths step-size sequences, improves tolerance proportionality, and reduces computational cost compared with r across the ODE tests.The reported comparison is summarized in Table 1, which counts time steps after final refinement for different tolerances.Source: §3.2.3 · p. 11, Table 1 · p. 11
3.3 PDE Test Problems and Related Results
- Both linear and nonlinear diffusion tests show good tolerance proportionality and computational stability, with the expected runtime reduction under parallelization.The experiments use rmod with c = 0.4.Source: §3.3 · p. 11, Figure 13 · p. 12
4 Discussion
The discussion favors rmod as a stable, reliable choice for adaptive MGRIT Runge–Kutta methods, while identifying initial partitioning and stiff problems as constraints and targets for further work.
4.1 Advantages
- The refinement factor rmod is preferred over r qualitatively and quantitatively, and the PDE tests show lower computational cost than sequential methods beyond a processor threshold.The discussion also reports that the computational-stability quality indicators are satisfied for both rmod and r.Source: §4.1 · p. 12
4.2 Limitations
- Each test problem requires an appropriate initial subinterval partitioning for MGRIT to achieve computational stability.The authors compare this choice to selecting an initial step size in a sequential algorithm.Source: §4.2 · p. 13
- Satisfactory results currently cover nonstiff or mildly stiff problems; greater step-size variation makes stiff cases more challenging, although heuristics improved the sequence.The stiff van der Pol example uses μ = 30 and initial value [1.5, 3] over [0, 10].Source: §4.2 · pp. 13–14, Figure 15 · p. 14
4.3 Future Research
- Further work should examine the heuristic, investigate stiffness-indicator switching, and develop methods specifically designed for stiff problems.The authors identify these as directions for improving results on stiff problems within the current framework.Source: §4.3 · p. 14
Funding and Acknowledgements
The authors acknowledge program support, technical assistance with initial XBraid runs, and access to the Komondor HPC facility.
Funding and Acknowledgements
- The work received support from the Ministry of Innovation and Technology NRDI Office and the Artificial Intelligence National Laboratory Program.Support also came through the Thematic Excellence Program ELTE TKP 2021-NKTA-62.Source: Funding and Acknowledgements · p. 14
- The authors thank Sidafa Conde for assistance with the initial XBraid runs.Conde is identified as a former Senior Member of Technical Staff at Sandia National Laboratories.Source: Funding and Acknowledgements · p. 14
- Digital Government Development and Project Management Ltd. awarded the authors access to the Komondor HPC facility in Hungary.Source: Funding and Acknowledgements · p. 14