A Block Toeplitz Preconditioner for All-At-Once Systems from Linear Wave Equations

In this work, we propose a novel parallel-in-time preconditioner for an all-at-once system, arising from the numerical solution of linear wave equations. Namely, our main result concerns a block tridiagonal Toeplitz preconditioner that can be diagonalized via fast sine transforms, whose effectiveness is theoretically shown for the nonsymmetric block Toeplitz system resulting from discretizing the concerned wave equation. Our approach is to first transform the original linear system into a symmetric one and subsequently develop the desired preconditioning strategy based on the spectral symbol of the modified matrix. Various Krylov subspace methods are considered. That is, we show that the minimal polynomial of the preconditioned matrix is of low degree, which leads to fast convergence when the generalized minimal residual method is used. To fully utilize the symmetry of the modified matrix, we additionally construct an absolute-value preconditioner which is symmetric positive definite. Then, we show that the eigenvalues of the preconditioned matrix are clustered around±1, which gives a convergence guarantee when the minimal residual method is employed. Numerical examples are given to support the effectiveness of our preconditioner. Our block Toeplitz preconditioner provides an alternative to the existing block circulant preconditioner proposed by McDonald, Pestana, and Wathen in [SIAM J. Sci. Comput., 40 (2018), pp. A1012-A1033], advancing the symmetrization preconditioning theory that originated from the same work.