ParaDiag: parallel-in-time algorithms based on the diagonalization technique

arXiv2005.09158MaRDI QIDQ6340985FDOQ6340985

Jun Liu, Xiaoqiang Yue, Martin J. Gander, Shulin Wu, Tao Zhou

Publication date: 18 May 2020

Abstract: 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. ParaDiagalgorithms in the literature can be classified into two groups: ParaDiag-I: direct standalone solvers, 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. 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 and and we compare these results to the performance of parareal and MGRiT, two widely used PinT algorithms.

Has companion code repository: https://github.com/wushulin/ParaDIAG

This page was built for publication: ParaDiag: parallel-in-time algorithms based on the diagonalization technique

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6340985)