Maths

The PFASST algorithm is, in some ways, similar to the parareal method for the temporal parallelization of ODEs and PDEs. These methods 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

\[u(t) = u_0 + \int_0^t f(\tau,u(\tau)) \,d\tau\]

from \(t_n\) to \(t_{n+1}\) (that is, \(\dot{u} = f(u,t)\)). 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.

For PDEs, it may be the case that the coarse and fine propagators differ only in their level of refinement (in the spatial and/or temporal directions).

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 SDC time-integration technique in a novel way to improve the parallel efficiency of the method. However, the general structure and roles of the fine and coarse propagators are the same as the parareal method.

Furthermore, the PFASST algorithm adds corrections to the coarse propagator in a manner reminiscent of FAS corrections for non-linear multi-grid methods.

References