Parareal

Parareal is a parallel algorithm from numerical analysis and used for the solution of initial value problems.It was introduced in 2001 by Lions, Maday and Turinici. Since then, it has become one of the most widely studied parallel-in-time integration methods. Parareal is a parallel algorithm from numerical analysis and used for the solution of initial value problems.It was introduced in 2001 by Lions, Maday and Turinici. Since then, it has become one of the most widely studied 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. 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.