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

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.