What are the differences between Parareal, PITA, and PFASST?

Question

The Parareal, PITA, and PFASST algorithms are all across-the-domain techniques for parallelizing the solution of time-dependent problems in time.

1. What are the guiding principles behind these methods?

2. What are the main differences between them?

3. Can I say that one is based on another? How?

4. What about their applications?

I know there will be no answer to the question "which is better?", but a good understanding of their application areas and validation conditions is helpful to me.

Answer 1

These methods can be roughly described in terms of two time-stepping methods, denoted here by $G$ and $F$. Both $G$ and $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 $G$ propagator is computationally less expensive than the $F$ propagator, and hence $G$ is typically a low-order method. Since the overall accuracy of the methods is limited by the accuracy of the $F$ propagator, $F$ is typically higher-order and in addition may use a smaller time step than $G$. For these reasons, $G$ is referred to as the coarse propagator and $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, using the coarse propagator. The Parareal method then proceeds iteratively, alternating between the parallel computation of $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} = G(t_{n+1}, t_n, U_n^{k+1}) + F(t_{n+1}, t_n, U_n^k) - 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. Note that at this point we haven't specified what the $G$ and $F$ propagators are: they could be, for example, Runge-Kutta schemes of varying order.

The PITA method is very similar to Parareal, but it keeps track of previous updates and only updates the initial condition on each processor in a manner reminiscent of Krylov subspace methods. This allows PITA to solve linear second-order equations which Parareal cannot.

The PFASST method differs from the Parareal and PITA methods in two fundamental ways: first, it relies on the iterative Spectral Deferred Correction (SDC) time-stepping scheme, and second it incorporates Full Approximation Scheme corrections to the coarse propagator, and in fact PFASST can use a hierarchy of propagators (instead of just two). Using SDC allows the time-parallel and SDC iterations are hybridized which relaxes the efficiency constraints of Parareal and PITA. Using FAS corrections enables a lot of flexibility when constructing the coarse propagators of PFASST (making the coarse propagators as cheap as possible helps increase parallel efficiency). Coarsening strategies include: time-coarsening (fewer SDC nodes), space-coarsening (for grid based PDEs), operator coarsening, and reduced physics.

I hope this outlines the fundamentals, differences, and similarities between the algorithms. Please see the references in this post for more details.

Regarding applications, the methods have been applied to a wide variety of equations (planetary orbits, Navier-Stokes, particle systems, chaotic systems, structural dynamics, atmospheric flows etc etc). When applying time-parallelization to a given problem you should certainly validate the method in a manner appropriate for the problem being solved.