Jun 10 – 11, 2022
Dipartimento di Matematica, Università di Pisa
Europe/Rome timezone

Improved parallel-in-time integration via low-rank updates and interpolation

Jun 11, 2022, 10:15 AM
Aula Magna (Dipartimento di Matematica, Università di Pisa)

Aula Magna

Dipartimento di Matematica, Università di Pisa

L.go B. Pontecorvo, 5 56127 Pisa (PI) Italy


Daniel Kressner (EPFL)


This talk is concerned with linear matrix equations that arise from the space-time discretization of time-dependent linear partial differential equations (PDEs). Such matrix equations have been considered, for example, in the context of parallel-in-time integration leading to a class of algorithms called ParaDiag, see [1] and the references therein. In this talk, we describe and analyze two novel approaches for the numerical solution of such equations. Our first approach is based on the
observation that the modification of these equations performed by ParaDiag in order to solve them in parallel has low rank. Building upon previous work on low-rank updates of matrix equations [2], this allows us to make use of tensorized Krylov subspace methods or the techniques from [4] to account for the modification. Our second approach is based on
interpolating the solution of the matrix equation from the solutions of several modifications. Both approaches avoid the use of iterative refinement needed by ParaDiag and related space-time approaches [3] in order to attain good accuracy. In turn, our new approaches have the potential to outperform, sometimes significantly, existing approaches. This potential is demonstrated for several different types of PDEs.


[1] 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, 2020.
[2] D. Kressner, S. Massei, and L. Robol. Low-rank updates and a divide-and-conquer method for linear matrix equations. SIAM J. Sci. Comput., 41(2):A848–A876, 2019.
[3] E. McDonald, J. Pestana, and A. Wathen. Preconditioning and iterative solution of all-at-once systems for evolutionary partial differential equations. SIAM J. Sci. Comput., 40(2):A1012–A1033, 2018.
[4] D. Palitta. Matrix equation techniques for certain evolutionary partial differential equations. J. Sci. Comput., 87(3):Paper No. 99, 36, 2021.

Presentation materials

There are no materials yet.