ParaDiag is a collection of diagonalization-based parallel-in-time (PinT) algorithms and can be categorized into two classes:

Direct ParaDiag algorithms

Iterative ParaDiag algorithms

The general idea for all the ParaDiag algorithms is to form the difference equations arising from some time discretization (e.g., the backward Euler method or the trapezoidal rule) into an all-at-once system and then solve such a system directly or iteratively. Maday and Rønquist first introduced this idea in [1].

For direct ParaDiag algorithms, we diagonalize the time discretization matrix and decouple the all-at-once system into a series of sub-systems, which can be solved in parallel across all time levels. The research for direct ParaDiag algorithms focuses on making the time discretization matrix be diagonalizable and making the condition number of the eigenvector matrix as small as possible. For the iterative ParaDiag algorithms, we precondition the all-at-once system by a block α-circulant matrix and solve the preconditioning step for each iteration via a block Fourier spectral factorization.

ParaDiag algorithms can handle both dissipative and hyperbolic equations (such as acoustic equations and the Schrödinger equations). An introductory document in this field is [2], where the reader can find variants, applications and some representative theoretical results of ParaDiag. This document will be updated regularly when new interesting progress appears.

MadayRonquist2008

Y. Maday and E. M. Rønquist, “Parallelization in time through tensor-product space-time solvers,” Comptes Rendus Mathematique, vol. 346, no. 1–2, pp. 113–118, 2008, doi: 10.1016/j.crma.2007.09.012. [Online]. Available at: http://dx.doi.org/10.1016/j.crma.2007.09.012

BibTeX entry MadayRonquist2008

@article{MadayRonquist2008,
author = {Maday, Yvon and Rønquist, Einar M.},
doi = {{10.1016/j.crma.2007.09.012}},
journal = {Comptes Rendus Mathematique},
number = {1--2},
pages = {113--118},
title = {{Parallelization in time through tensor-product space-time solvers}},
url = {{http://dx.doi.org/10.1016/j.crma.2007.09.012}},
volume = {346},
year = {2008}
}

GanderEtAl2021

M. J. Gander, J. Liu, S.-L. Wu, X. Yue, and T. Zhou, “ParaDiag: parallel-in-time algorithms based on the diagonalization technique,” arXiv preprint arXiv:2005.09158, 2021 [Online]. Available at: http://arxiv.org/abs/2005.09158

BibTeX entry GanderEtAl2021

@unpublished{GanderEtAl2021,
author = {Gander, Martin J and Liu, Jun and Wu, Shu-Lin and Yue, Xiaoqiang and Zhou, Tao},
howpublished = {arXiv preprint arXiv:2005.09158},
title = {ParaDiag: parallel-in-time algorithms based on the diagonalization technique},
url = {http://arxiv.org/abs/2005.09158},
year = {2021}
}

Abstract for BibTeX entry GanderEtAl2021

In 2008, Maday and Rønquist 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 \em ParaDiag algorithms. ParaDiag algorithms in the literature can
be classified into two groups:
\beginitemize
\item ParaDiag-I: direct standalone solvers,
\item ParaDiag-II: iterative solvers.
\enditemize
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. We show the main known
theoretical results in each case, and also provide Matlab codes for testing. The goal of the Matlab
codes is to help the interested reader understand the key features of the ParaDiag algorithms,
without intention to be highly tuned for efficiency and/or low memory use.
We also provide speedup measurements of ParaDiag algorithms for a 2D linear advection-diffusion equation.
These results are obtained on the Tianhe-1 supercomputer in China and the SIUE Campus Cluster in the US,
which is a multi-array, configurable and cooperative parallel system, and we compare these results to the
performance of parareal and MGRiT, two widely used PinT algorithms. In a forthcoming update of this note,
we will provide more material on ParaDiag algorithms, in particular further Matlab codes and parallel
computing results, also for more realistic applications.