Summary

• The Parareal gives significant speedup for nonlinear systems of ODEs and discretized diffusive PDEs but reported to be less effective for hyperbolic problems.

• One of the key applications of parallel time integration is weather forecasting. The Parareal algorithm has proved to achieve substantial speedup when used for Lorentz equation.

• This paper studies the application of the Parareal algorithm on the advection equation using method of characteristics and it also studies applying parareal on the the wave equation. In the former case, some speed up can be achieved but with very low efficiency (Parareal is not the ideal for this type of problems) and in the second case the number of iterations is equal to the number of time subdomain (i.e. no speed up gain).

• In the context of hyperbolic problems, interesting modifications has been introduced to the parareal algorithm to achieve better results in work done by Cortial and Farhat (ref 5,7 in the paper) and further analysis is found (ref 10 in the paper) by Gander.

• The paper derives the parareal algorithm (many details are similar to those in the “The Parareal algorithm: A survey of present work” by G. Staff).

• The paper then proves the convergence of the Parareal algorithm when applied to the constant coefficients advection in a bounded domain and the results can be generalized to the variable coefficient form.

• There is one assumption about the coarse solution \(G\) of the advection equation in the analysis conducted by this paper. Which is stated as: “Assumption 1: There exist a positive constant \(\tilde{a}\), \(0<\tilde{a}\le a\), such that \(G(T_{n+1}, T_n,U_n)\) at \(x\) only depends on the boundary condition \(g\) and on \(U_n(x-\tilde{a}\Delta T_n)\) for \(x-\tilde{a}\Delta T_n\ge 0\)”, where
  • we have \(N\) subintervals in time, each starts at \(T_n\) and ends at \(T_{n+1}\) with length \(\Delta T_n\), for \(n = 0,1, ..., N-1\),
  • \(U_n\) is the solution at \(T_n\),
  • \(a\) is the wave speed in the advection equation,
  • \(G(T_{n+1}, T_n,U_n)\) is the course approximation of the solution at \(T_{n+1}\).
• The convergence rate of the advection equation was then derived to be
  \(\sum_{n=0}^N ||u(.,T_n)-U_n^k||_1\) \(\le\) \(C \max(L-k\tilde{a}\Delta T,0)\times \max(N-k,0) \) where:
  • \(u(x,t)\) is the exact solution and \(U_n^k\) is the approximate solution at \(T_n\) and iteration \(k\),
  • the spacial domain is \(\Omega = (0,L)\),
  • \(\Delta T\) is the smallest interval of all \(\Delta T_n\) and
  • \(C\) is a constant defined as follows: \(C = max_{n=1,2,...,N}||u(.,T_n)-U_n^0||_\infty\).

Note that this rate of convergence is relative to the fine solution, \(F\), which is not necessarily the exact solution.

• For the advection equation, two numerical experiments where made in this paper on the homogenous advection equation \(u_t + u_x = 0\). The first order upwind scheme was used. The difference between the two experiments is in the discretization, where in the first experiment the coarse discretization satisfies the CFL condition exactly, \(a\frac{\Delta T}{\Delta X} = 1\), and thus assumption 1 was satisfied. In the second experiment, the ratio was \(a\frac{\Delta T}{\Delta X} \approx 0.923\), and hence assumption 1 was not satisfied as in each grid point, the scheme uses information from the same grid point one step earlier in time. The first test took about 6 iterations to converge and remove the error totally (we have 12 subintervals in time). And in the second experiment it took more than 7 iteration to converge (we have 13 subintervals in time in this experiment). This difference in convergence behavior is due to the satisfiability of assumption 1.

• I tried to calculate the speed up gain for the first advection experiment using the results in the paper and I got that the speed up \(= 1.9\approx 2\) and the parallel efficiency is about \(0.16\) using \(12\) processors. Which might be considered inefficient in some contexts.

• They tested the algorithm on the wave equation to prove its inadequacy for this type of problems. A main difference between the advection equation and the wave equation is that the solution of the former at later times will not depend on the initial condition while the solution of the later equation does depend on the initial condition. Thus the number of iterations required is equal to the number of time subdomains with no gain in speed up.

Things I’d like to understand:

• In the constant coefficient case with the CFL number satisfied exactly, do we always have \(\tilde{a} = a\)?
• I could not understand from the equation of the transparent b.c how they work in this way (waves arrives at the boundaries are absorbed, equation 11)?

• How does the multiple shooting method related to the parareal (I’ll probably check some references later, ref 1 below)?

• In page 23 of the paper the paragraph below equation 5 it says, “However in general, it is too expensive to compute the Jacobian terms in (5) exactly”. In general we do not have exact equation for \(\varphi\), thus we do not know \(\varphi'\), am I right?

Future

• Can we make use of the paper (ref 3 below) to enhance the parallel efficiency of the parallel time integration of hyperbolic problems (I need to check that paper)?

• The topic of this paper seems interesting (ref 4 below) (I need to go through it)

Related Literature

1. M. Kiehl, “Parallel multiple shooting for the solution of initial value problems,” Parallel Com- puting, vol. 20, pp. 275–295, 1994.

2. M. J. Gander and E. Hairer, “Nonlinear convergence analysis for the parareal algorithm,”

3. G. Bal, “Parallelization in time of (stochastic) ordinary differential equations,”

4. I. Tarrass, L. Giraud, and P. Thore, “Time domain decomposition for the solution of the acoustic wave equation on locally refined meshes,”