Maths

The Parallel Full Approximation Scheme in Spact and Time (PFASST) algorithm is time-parallel (across the domain) algorithm for marching time-dependent ODEs or PDEs through time.

The PFASST algorithm is perhaps most easily understood as a parallel version of the multi-level Spectral Deferred Correction (MLSDC) scheme (see below). Some aspects of PFASST are also reminiscent of the Parareal algorithm (see below).

MLSDC

XXX

Parareal

The Parareal method can be roughly described in terms of two numerical approximation methods, denoted here by \(\mathcal{G}\) and \(\mathcal{F}\). Both \(\mathcal{G}\) and \(\mathcal{F}\) propagate an initial value \(U_n \approx u(t_n)\) by approximating the solution to

\[\dot{u} = f(u,t), \quad u(t_n) = u_n\]

from \(t_n\) to \(t_{n+1}\). For the methods to be efficient, it must be the case that the \(\mathcal{G}\) propagator is computationally less expensive than the \(\mathcal{F}\) propagator, and hence \(\mathcal{G}\) is typically a low-order method. Since the overall accuracy of the methods is limited by the accuracy of the \(\mathcal{F}\) propagator, \(\mathcal{F}\) is typically higher-order and in addition may use a smaller time step than \(\mathcal{G}\). For these reasons, \(\mathcal{G}\) is referred to as the coarse propagator and \(\mathcal{F}\) the fine propagator.

The parareal method begins by computing a first approximation \(U_{n+1}^0\) for \(n = 0 \ldots N-1\) where \(N\) is the number of time steps, often performed with the coarse propagator:

\[U_{n+1}^0 = \mathcal{G}(t_{n+1}, t_{n}, U_n^0).\]

The Parareal method then proceeds iteratively, alternating between the parallel computation of \(\mathcal{F}(t_{n+1},t_n,U_n^k)\) and an update of the initial conditions at each processor of the form

\[U_{n+1}^{k+1} = \mathcal{G}(t_{n+1}, t_n, U_n^{k+1}) + \mathcal{F}(t_{n+1}, t_n, U_n^k) - \mathcal{G}(t_{n+1}, t_n, U_n^{k})\]

for \(n = 0 \ldots N-1\). That is, the fine propagator is used to refine the solution in each time slice in parallel, while the coarse propagator is used to propagate the refinements performed by the fine propagator through time to later processors.

The PFASST method operaters in a similar manner to the Parareal method, but it employs the MLSDC time-integration technique in a novel way to improve the parallel efficiency of the method.

References