Five Decades of Time Parallel Time Integration: Best Current Methods for Parabolic and Hyperbolic Problems

A image


Advanced Numerical Methods for Scientific Computing
Martin Gander
Section de Mathématiques, Université de Geneve
Thursday 14th December 2017
Aula Consiglio VII Piano - Edificio 14, Dipartimento di Matematica POLITECNICO DI MILANO
Time parallel time integration methods have received renewed interest over the last decade 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 over the past five 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. Contact:
Martin J. Gander obtained his undergraduate degree from ETH Zürich in 1993, and his PhD from Stanford University in 1997. He then spent two years as a postdoctoral fellow at Ecole Polytechnique in Paris, before becoming professor of Mathematics at McGill University in 1999. In 2004, he followed the call by the University of Geneva for a full professorship in Mathematics. His main interests are numerical analysis, in particular parallel iterative methods for space-time problems.