Optimal block circulant preconditioners for block Toeplitz systems with application to evolutionary PDEs

Research output: Contribution to journalJournal articlepeer-review

1 Citation (Scopus)


In this work, we propose a preconditioned minimal residual (MINRES) method for a class of non-Hermitian block Toeplitz systems. Namely, considering an mn-by-mn non-Hermitian block Toeplitz matrix T(n,m) with m-by-m commuting Hermitian blocks, we first premultiply it by a simple permutation matrix to obtain a Hermitian matrix and then construct a Hermitian positive definite block circulant preconditioner for the modified matrix. Under certain conditions, we show that the eigenvalues of the preconditioned matrix are clustered around ±1 when n is sufficiently large. Due to the Hermitian nature of the modified matrix, MINRES with our proposed preconditioner can achieve theoretically guaranteed superlinear convergence under suitable conditions. In addition, we provide several useful properties of block circulant matrices with commuting Hermitian blocks, including diagonalizability and symmetrization. A generalization of our result to the multilevel block case is also provided. We in particular indicate that our work can be applied to the all-at-once systems arising from solving evolutionary partial differential equations. Numerical examples are given to illustrate the effectiveness of our preconditioning strategy.

Original languageEnglish
Article number113965
JournalJournal of Computational and Applied Mathematics
Early online date28 Dec 2021
Publication statusPublished - Jun 2022

Scopus Subject Areas

  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • All-at-once systems
  • Block matrices
  • Circulant preconditioners
  • Evolutionary partial differential equations
  • Singular value/eigenvalue distribution
  • Toeplitz/Hankel matrices


Dive into the research topics of 'Optimal block circulant preconditioners for block Toeplitz systems with application to evolutionary PDEs'. Together they form a unique fingerprint.

Cite this