Talk

Six Decades of Time Parallel Time Integration: Best Current Methods for Parabolic and Hyperbolic Problems
Martin J. Gander (Université de Genève)

Time parallel time integration methods have received renewed interest over the last two decades because of the advent of massively parallel computers, due to the clock speed limit reached on today's processors. When solving time dependent partial differential equations, the time direction is usually not used for parallelization. But when parallelization in space saturates, the time direction offers itself as a further direction for parallelization. The time direction is however special, and for evolution problems there is a causality principle: the solution later in time is determined by the solution earlier in time, so the flow of information is just into the direction forward in time. Algorithms trying to use the time direction for parallelization must therefore be special, and take this very different property of the time dimension into account.

I will show in this talk how time parallel time integration methods were invented and developed over the past six decades, and give a classification into four different groups: methods based on multiple shooting, space-time multigrid methods, methods based on domain decomposition and waveform relaxation, and direct time parallel methods. The performance of these methods depends on the nature of the underlying evolution problem, and it turns out that for the first two classes of methods, time parallelization is only really possible for parabolic problems, while the last two classes can also be used to parallelize hyperbolic problems in time. I will also explain in more detail one of the methods from each class: the parareal algorithm and a space-time multigrid method, which are currently among the most promising methods for parabolic problems, and a Schwarz waveform relaxation method related to tent-pitching and a direct time parallel method based on diagonalization of the time stepping matrix, which are very effective for hyperbolic problems.

Slides [talk]