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.

  1. 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 [Online]. Available at: http://dx.doi.org/10.1016/j.crma.2007.09.012 
    @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}
}
  2. 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 
    @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}
}