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.

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

The Problem The goal is to solve an initial value problem of the form

d u d t = f ( t , u ) over t ∈ [ t 0 , T ] with u ( t 0 ) = u 0 . {\displaystyle {\frac {\mathrm {d} u}{\mathrm {d} t}}=f(t,u)\quad {\text{over}}\quad t\in [t_{0},T]\quad {\text{with}}\quad u(t_{0})=u^{0}.}

The right hand side f {\displaystyle f} is assumed to be a smooth (possibly nonlinear) function. It can also correspond to the spatial discretization of a partial differential equation in a method of lines approach. We wish to solve this problem on a temporal mesh of N + 1 {\displaystyle N+1} equally spaced points ( t 0 , t 1 , … , t N ) {\displaystyle (t_{0},t_{1},\ldots ,t_{N})} , where t j + 1 = t j + Δ T {\displaystyle t_{j+1}=t_{j}+\Delta T} and Δ T = ( T − t 0 ) / N {\displaystyle \Delta T=(T-t_{0})/N} . Carrying out this discretisation we obtain a partitioned time interval consisting of time slices [ t j , t j + 1 ] {\displaystyle [t_{j},t_{j+1}]} for j = 0 , … , N − 1 {\displaystyle j=0,\ldots ,N-1} . The objective is to calculate numerical approximations U j {\displaystyle U_{j}} to the exact solution u ( t j ) {\displaystyle u(t_{j})} using a serial time-stepping method (e.g. Runge-Kutta) that has high numerical accuracy (and therefore high computational cost). We refer to this method as the fine solver F {\displaystyle {\mathcal {F}}} , which propagates an initial value U j {\displaystyle U_{j}} at time t j {\displaystyle t_{j}} to a terminal value U j + 1 {\displaystyle U_{j+1}} at time t j + 1 {\displaystyle t_{j+1}} . The goal is to calculate the solution (with high numerical accuracy) using F {\displaystyle {\mathcal {F}}} such that we obtain

… excerpt ends here. Continue reading the full article.