The parareal algorithm introduced in 2001 by Lions, Maday, and Turinici is an
iterative method for the parallelization of the numerical solution of ordinary
differential equations or partial differential equations discretized in the temporal
direction. The temporal interval of interest is partitioned into successive domains
which are assigned to separate processor units. Each iteration of the parareal
algorithm consists of a high accuracy solution procedure performed in parallel on
each domain using approximate initial conditions and a serial step which propagates
a correction to the initial conditions through the entire time interval. The
original method is designed to use classical single-step numerical methods
for both of these steps. This paper investigates a variant of the parareal
algorithm first outlined by Minion and Williams in 2008 that utilizes a deferred
correction strategy within the parareal iterations. Here, the connections between
parareal, parallel deferred corrections, and a hybrid parareal-spectral deferred
correction method are further explored. The parallel speedup and efficiency
of the hybrid methods are analyzed, and numerical results for ODEs and
discretized PDEs are presented to demonstrate the performance of the hybrid
approach.
Keywords
parallel in time, parareal, ordinary differential
equations, parallel computing, spectral deferred
corrections