Wavelet-In-Time Multigrid-In-Space Preconditioning of Parabolic Evolution Equations

Two space-time variational formulations of linear parabolic evolution equations are considered: one is symmetric and elliptic on the trial space, while the other is not. In each case, a space-time Petrov--Galerkin discretization using suitable tensor product trial and test functions leads to a large linear system of equations. The well-posedness of this system with respect to parabolic norms induces a canonical preconditioner for the algebraic equations that arise after a choice of basis. For the iterative resolution of this algebraic system with parallelization in the temporal direction, we propose a sparse algebraic wavelet-in-time transformation on possibly nonuniform temporal meshes. This transformation approximately block-diagonalizes the preconditioner, and the individual spatial blocks can then be inverted, for instance, by standard spatial multigrid methods in parallel. The performance of the preconditioner is documented in a series of numerical experiments.