A Family of Block Preconditioners for Block Systems

The solution of block system A_mnx = b by the preconditioned conjugate gradient method where A_mn is an m-by-m block matrix with n-by-n Toeplitz blocks is studied. The preconditioner c_F⁽¹⁾ (A_mn) is a matrix that preserves the block structure of A_mn. Specifically, it is defined as the minimizer of ||A_mn - C_mn ||_F over all m-by-m block matrices C_mn with n-by-n circulant blocks. We prove that if A_mn is positive definite, then c_F⁽¹⁾(A_mn) is positive definite too. We also show that c_F⁽¹⁾(A_mn) is a good preconditioner for solving separable block systems with Toeplitz blocks and quadrantally symmetric block Toeplitz systems. We then discuss some of the spectral properties of the operator c_F⁽¹⁾. In particular, we show that the operator norms ||c_F⁽¹⁾||₂ = ||c_F⁽¹⁾||_F = 1.