Martin J. Gander
University of Geneva

Multiple Shooting, Parareal, Krylov Parareal, ParaExp and Space-Time
 Multigrid: an Overview on Time Domain Decomposition Methods

 Many problems in science and engineering are time dependent, and time
 stepping methods are used to obtain approximate solutions. If the
 problems are large scale, or solutions are needed in real time, it is
 necessary to use the computing power of parallel computers. The
 classical strategy to parallelize time integration is to parallelize
 the solution at each time step, and to advance sequentially from time
 step to time step. This approach however neglects an entire dimension,
 the time dimension, which could also be used for the parallelization.
 In contrast to the spatial dimensions, the time dimension has however
 a direction: the solution later in time depends only on the solution
 earlier in time, and not vice versa. It therefore seems difficult to
 do useful computations at a future time step, before the present time
 step results are known.

 There are several algorithms which nevertheless try to do useful
 computations later in time, before fully accurate results at the
 present time step are available, and one of the more recent ones is
 based on multiple shooting: the parareal algorithm. This algorithm is
 using an approximation of the Jacobian on a coarse grid in the Newton
 iteration classically used for solving the shooting equations. After
 reviewing a compact convergence result for this algorithm, I will
 illustrate its numerical performance for several examples of systems
 of ordinary and partial differential equations. These examples reveal
 that while the algorithm performs well for diffusive problems,
 convergence is unsatisfactory for hyperbolic equations. I will then
 explain as possible remedies for this problem the Krylov parareal
 algorithm, and also a different time parallel method called ParaExp. I
 will finally show two further developments, a space-time algorithm
 based entirely on multigrid techniques, and a space-time algorithm
 based on space-time domain decomposition.