ON THE SPECTRUM OF A FAMILY OF PRECONDITIONED BLOCK TOEPLITZ MATRICES

Research on preconditioning Toeplitz matrices with circulant matrices has been active recently. The preconditioning technique can be easily generalized to block Toeplitz matrices. That is, for a block Toeplitz matrix T consisting of N x N blocks with M x M elements per block, a block circulant matrix R is used with the same block structure as its preconditioner. In this research, the spectral clustering property of the preconditioned matrix R-1T with T generated by two-dimensional rational functions T(z(x), z(y)) of order (p(x), q(x), p(y), q(y)) is examined. It is shown that the eigenvalues of R-1T are clustered around unity except at most O(M-gamma(y) + N-gamma(x)) outliers, where gamma(x) = max(p(x), q(x)) and gamma(y) = max(p(y), q(y)). Furthermore, if T is separable, the outliers are clustered together such that R-1T has at most (2-gamma(x) + 1)(2-gamma(y) + 1) asymptotic distinct eigenvalues. The superior convergence behavior of the preconditioned conjugate gradient (PCG) method over the conjugate gradient (CG) method is explained by a smaller condition number and a better clustering property of the spectrum of the preconditioned matrix R-1T.