Parareal
Parareal is a parallel algorithm from numerical analysis and used for the solution of initial value problems.
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.
[8][9] Parareal is a widely studied method and has been used and modified for a range of different applications.
[10] 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.
It can also correspond to the spatial discretization of a partial differential equation in a method of lines approach.
The problem with this (and the reason for attempting to solve in parallel in the first place) solution is that it is computationally infeasible to calculate in real-time.
Instead of using a single processor to solve the initial value problem (as is done with classical time-stepping methods), Parareal makes use of
Parareal makes use of a second time-stepping method to solve this initial value problem in parallel, referred to as the coarse solver
Firstly, run the coarse solver serially over the entire time interval
Next, run the fine solver on each of the time slices, in parallel, from the most up-to-date solution values:
At this stage, one can use a stopping criterion to determine whether the solution values are no longer changing each iteration.
If this critertion is not satisfied, subsequent iterations can then be run by applying the fine solver in parallel and then the predictor-corrector.
Parareal should reproduce the solution that is obtained by the serial application of the fine solver and will converge in a maximum of
Typically, some form of Runge-Kutta method is chosen for both coarse and fine integrator, where
can also use a coarser spatial discretization, but this can negatively impact convergence unless high order interpolation is used.
[13] 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.
This includes in particular the assumption that all time slices are of identical length and that both coarse and fine integrator use a constant step size over the full simulation.
the computing time required for a single step of the fine and coarse methods, respectively, and assume that both are constant.
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
[14] Even though the formal analysis by Gander and Vandewalle covers only linear problems with constant coefficients, the problem also arises when Parareal is applied to the nonlinear Navier–Stokes equations when the viscosity coefficient becomes too small and the Reynolds number too large.
[17] Originally, the idea was formulated for the parallel implicit time-integrator PITA,[19] a method closely related to Parareal but with small differences in how the correction is done.
This version of Parareal can also stably integrate linear hyperbolic partial differential equations.
[18] A method with improved parallel efficiency based on a combination of Parareal with spectral deferred corrections (SDC) [22] has been proposed by M.
[23] It limits the choice for coarse and fine integrator to SDC, sacrificing flexibility for improved parallel efficiency.
The Parareal-SDC hybrid has been further improved by addition of a full approximation scheme as used in nonlinear multigrid.
This led to the development of the parallel full approximation scheme in space and time (PFASST).
[24] Performance of PFASST has been studied for PEPC, a Barnes-Hut tree code based particle solver developed at Juelich Supercomputing Centre.
Simulations using all 262,144 cores on the IBM BlueGene/P system JUGENE showed that PFASST could produce additional speedup beyond saturation of the spatial tree parallelisation.
[25] The multigrid reduction in time method (MGRIT) generalises the interpretation of Parareal as a multigrid-in-time algorithms to multiple levels using different smoothers.
The XBraid library implementing MGRIT is being developed by Lawrence Livermore National Laboratory.
