ParaDIAG: Parallel-in-Time Algorithms Based on the Diagonalization Technique

Shu-lin Wu (Northeast Normal University)

In 2008, Maday and Ronquist introduced an interesting new approach for the direct parallel-in-time (PinT) solution of time-dependent PDEs. The idea is to diagonalize the time stepping matrix, keeping the matrices for the space discretization unchanged, and then to solve all time steps in parallel. Since then, several variants appeared, and we call these closely related algorithms ParaDIAG algorithms. ParaDIAG algorithms in the literature can be classified into two groups: ParaDIAG-I: direct standalone solvers, and ParaDIAG-II: iterative solvers.

We will explain the basic features of each group in this note. To have concrete examples, we will introduce ParaDIAG-I and ParaDIAG-II for the advection-diffusion equation. We will also introduce ParaDIAG-II for the wave equation and an optimal control problem for the wave equation. We could have used the advection-diffusion equation as well to illustrate ParaDIAG-II, but wave equations are known to cause problems for certain PinT algorithms and thus constitute an especially interesting example for which ParaDIAG algorithms were tested. In this talk, we try to explain the main idea and the main known theoretical results in each case together with some numerical results.