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

Sean Hon*, Stefano Serra-Capizzano

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

3 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)177-195
Number of pages19
JournalElectronic Transactions on Numerical Analysis
Publication statusPublished - 13 Feb 2023

Scopus Subject Areas

  • Analysis
  • Applied Mathematics

User-Defined Keywords

  • all-at-once discretization
  • block circulant preconditioners
  • fast sine transforms
  • Krylov subspace methods
  • parallelin- time
  • wave equations


Dive into the research topics of 'A Block Toeplitz Preconditioner for All-At-Once Systems from Linear Wave Equations'. Together they form a unique fingerprint.

Cite this