Parareal is a parallel algorithm from numerical analysis and used for the solution of initial value problems. It has been introduced in 2001 by Lions, Maday and Turinici. Since then, it has become one of the most widely studied parallel-in-time integration methods.
Contents
Parallel-in-time integration methods
In contrast to e.g. Runge-Kutta or multi-step methods, some of the computations in Parareal can be performed in parallel and Parareal is therefore one example of a parallel-in-time integration method. While historically most efforts to parallelize the numerical solution of partial differential equations focussed on the spatial discretization, in view of the challenges from exascale computing, parallel methods for temporal discretization have been identified as a possible way to increase concurrency in numerical software. Because Parareal computes the numerical solution for multiple time steps in parallel, it is categorized as a parallel across the steps method. This is in contrast to approaches using parallelism across the method like parallel Runge-Kutta or extrapolation methods, where independent stages can be computed in parallel or parallel across the system methods like waveform relaxation.
History
Parareal can be derived as both a multigrid method in time method or as multiple shooting along the time axis. Both ideas, multigrid in time as well as adopting multiple shooting for time integration, go back to the 1980s and 1990s. Parareal is a widely studied method and has been used and modified for a range of different applications. Ideas to parallelize the solution of initial value problems go back even further: the first paper proposing a parallel-in-time integration method appeared in 1964.
Algorithm
Parareal solves an initial value problem of the form
Here, the right hand side
Parareal now requires a decomposition of the time interval
Each time slice is assigned to one processing unit when parallelizing the algorithm, so that
Parareal is based on the iterative application of two methods for integration of ordinary differential equations. One, commonly labelled
Serial time integration with the fine method would then correspond to a step-by-step computation of
Parareal instead uses the following iteration
where
In the Parareal iteration, the computationally expensive evaluation of
Speedup
Under some assumptions, a simple theoretical model for the speedup of Parareal can be derived. Although in applications these assumptions can be too restrictive, the model still is useful to illustrate the trade offs that are involved in obtaining speedup with Parareal.
First, assume that every time slice
Under these two assumptions, the runtime for the fine method integrating over
The runtime of Parareal using
Speedup of Parareal then is
These two bounds illustrate the trade off that has to be made in choosing the coarse method: on the one hand, it has to be cheap and/or use a much larger time step to make the first bound as large as possible, on the other hand the number of iterations
that is by the inverse of the number of required iterations.
Instability for imaginary eigenvalues
The vanilla version of Parareal has issues for problems with imaginary eigenvalues. It typically only converges toward the very last iterations, that is as
Variants
There are multiple algorithms that are directly based or at least inspired by the original Parareal algorithm.
Krylov-subspace enhanced Parareal
Early on it was recognised that for linear problems information generated by the fine method
is defined and updated after every Parareal iteration. Denote as
As the number of iterations increases, the space
Hybrid Parareal spectral deferred corrections
A method with improved parallel efficiency based on a combination of Parareal with spectral deferred corrections (SDC) has been proposed by M. Minion. It limits the choice for coarse and fine integrator to SDC, sacrificing flexibility for improved parallel efficiency. Instead of the limit of
with
Multigrid reduction in time (MGRIT)
The multigrid reduction in time method (MGRIT) generalises the interpretation of Parareal as a multigrid-in-time algorithms to multiple levels using different smoothers. It is a more general approach but for a specific choice of parameters it is equivalent to Parareal. The XBraid library implementing MGRIT is being developed by Lawrence Livermore National Laboratory.
ParaExp
ParaExp uses exponential integrators within Parareal. While limited to linear problems, it can produce almost optimal parallel speedup.