Band preconditioners for block-Toeplitz-Toeplitz-block systems

Preconditioned conjugate gradient methods are employed to solve symmetric positive definite m-by-m block Toeplitz with n-by-n Toeplitz block systems A_m,nx = b where A_m,n are generated by 2π-periodic nonnegative functions with zeros. Serra has proposed using band block Toeplitz with band Toeplitz block matrices B_m,n, with their external and internal bandwidths independent of m and n as preconditioners. Serra showed that if the Hessians of the generating function at the zeros are positive definite, then the condition number of B⁻¹_m,nA_m,n is uniformly bounded by a constant independent of m and n, whereas the condition number of A_m,n tends to infinity as m and n tend to infinity. In this paper, we provide a method for deriving band preconditioners for block-Toeplitz-Toeplitz-block matrices. Numerical examples are given to illustrate the performance of the method.