Time Parallel Time Integration

A course by Martin J. Gander

Martin J. Gander, professor at University of Geneva and laureate of FSMP chair in 2022, is giving a mini-course entitled Time parallel Time integration that will take place at Institut Henri Poincaré (11 rue Pierre et Marie Curie 75005 Paris). He will be assisted by Thibaut Lunet (Technische Universität Hamburg.) Please registrer (link below) to attend the course.

Registration

Registration is compulsory both to attend the face-to-face course and to access the streaming.

Click here to reach the registration form. 

Dates and rooms

• Tuesday June 20:  Room 01 (ground floor)
• Tuesday June 27 : Room 01 (ground floor)
• Tuesday July 4: Room 01 (ground floor)
• Tuesday July 11: Room 314 (3^rd floor)

from 9:00 to 12:00.

At the end of each lecture, there will be time reserved for questions and discussions.

Streaming

All lectures will be broadcast live via Zoom.

 Zoom link:

https://us02web.zoom.us/j/87800141071

Registration is compulsory to receive the ID and password to access the streaming.

Source code used during the course

Here's the link to the source code and demos used in the course: https://github.com/tlunet/pint-workshops/ 

Abstract

Time parallel time integration methods have received renewed interest over the last two decades because of the advent of massively parallel computers, and also 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, never backward. 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 present an elementary introduction in this mini-course to the emerging research area of time parallel time integration, more recently also referred to as PinT (Parallel in Time) methods. The course is for PhD students and Postdoctoral Fellows, and also more advanced researchers interested in understanding this emerging field of numerical analysis. Talented masters students are also welcome.  It is based on a recent book project, completely self contained with no prerequisits, and is structured into five chapters:

1) Introduction: Historical introduction to the subject, presentation of the Dahlquist and Lorentz equations as model Ordinary Differential Equations (ODEs), and the time dependent heat equation, wave equation and transport equation as Partial Differential Equations (PDEs), model problems to be used throughout the course. Introduction of important concepts of stability and convergence.  Overview of the four basic techniques that will be used to construct time parallel methods: multiple shooting, domain decomposition and waveform relaxation, multigrid, and direct solvers.

2) Multiple Shooting Type Methods: Historical idea of Nievergelt from 1964 with mathematical properties of his method.  Multiple shooting in time with a convergence result. Introduction and analysis of the Parareal algorithm, proof of equivalence with multiple shooting. Convergence proofs for non-linear systems of ODEs and parabolic problems. Fundamental convergence problems for hyperbolic problems.

3) Domain Decomposition and Waveform Relaxation: Historical introduction starting with the method of successive approximations of Picard and the Lindelöf convergence analysis. Waveform relaxation methods for circuit simulation with detailed convergence analysis. Schwarz waveform relaxation methods with linear and superlinear convergence proofs for parabolic problems, and finite step convergence for wave equations. Optimized Schwarz waveform relaxation methods with optimization of transmission conditions and convergence proofs.

4) Time Multigrid Methods: Introduction to the first time parallel multigrid method of Hackbusch, called parabolic multigrid, with a convergence analysis showing why space coarsening is not possible. A time multigrid method for the Dahlquist equation with convergence analysis. The new space-time multigrid method of myself and Neumüller, including a detailed convergence analysis for the heat equation. Interpretations of Parareal as multigrid method, and also an introduction to the variant called Multigrid Reduction In Time (MGRIT) based on algebraic multigrid (AMG). Introduction to the Parallel Full Approximation Scheme in Space Time (PFASST).

5) Direct Space-Time Parallel Solvers: Complete historical development of such methods, including parallel predictor corrector methods, boundary value methods, time parallel time stepping, cyclic reduction, Laplace transforms, methods based on the diagonalization of the time stepping matrix, Revisionist Integrad Deferred Correction (RIDC), and ParaExp.