Time Parallel Time Integration

Le cours de Martin J. Gander

Martin J. Gander, professeur à l'Université de Genève et lauréat de la Chaire FSMP en 2022, donne un mini-cours intitulé Time Parallel, time integration, qui se tiendra sur quatre séances à l'Institut Henri Poincaré (11 rue Pierre et Marie Curie 75005 Paris). Il sera assisté de Thibaut Lunet (Technische Universität Hamburg). Entrée sur inscription.

Inscription

L'inscription est obligatoire pour accéder au cours en présentiel comme en distanciel (pour se connecter au streaming).

Cliquez ici pour accéder au formulaire d'inscription.

Dates des séances et salles

Mardi 20 juin : Salle 01 (RDC)
Mardi 27 juin : Salle 01 (RDC)
Mardi 4 juillet : Salle 01 (RDC)
Mardi 11 juillet : Salle 314 (3^e étage)

de 9h à 12h.

Un temps sera réservé aux questions et discussions à l'issue de chaque séance.

Le cours sera également accessible en live streaming.

Lien de connexion Zoom :

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

L'identifiant et le mot de passe nécessaires à la connexion vous serons communiqués uniquement après votre inscription.

Code source et démonstrations utilisées pendant le cours

Vous trouverez ici le code source et les démonstrations utilisées durant le cours: https://github.com/tlunet/pint-workshops/

Résumé du cours

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.