Preconditioners for block Toeplitz systems based on circulant preconditioners

We study the numerical solution of a block system T(m,n)x = b by preconditioned conjugate gradient methods where T-m,T-n is an m x m block Toeplitz matrix with n x n Toeplitz blocks. These systems occur in a variety of applications, such as two-dimensional image processing and the discretization of two-dimensional partial differential equations. In this paper, we propose new preconditioners for block systems based on circulant preconditioners. From level-1 circulant preconditioner we construct our first preconditioner q(1)(T-m,T-n) which is the sum of a block Toeplitz matrix with Toeplitz blocks and a sparse matrix with Toeplitz blocks. By setting selected entries of the inverse of level-2 circulant preconditioner to zero, we get our preconditioner q(2)(T-m,T-n) which is a (band) block Toeplitz matrix with (band) Toeplitz blocks. Numerical results show that our preconditioners are more efficient than circulant preconditioners.