The USC Andrew and Erna Viterbi School of Engineering USC Signal and Image Processing Institute USC Ming Hsieh Department of Electrical Engineering University of Southern California

Technical Report USC-SIPI-164

“On the Spectrum of a Family of Preconditioned Block Toeplitz Matrices”

by Takang Ku and C.-C. Jay Kuo

November 1990

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 × N blocks with M × M elements per block, we can use a block circulant matrix R with the same block structure as its preconditioner. In this research, we examine the spectral clustering property of the preconditioned matrix R-1T with T generated by two-dimensional rational functions T(zx, zy) of order (px, qx, py, qy). We show that the eigenvalues of R-1T are clustered around unity except at most O(M gy + N gx) outliers, where gx = max(px, qx) and gy = max(py, qy). Furthermore, if T is separable, the outliers are clustered together such that R-1T has at most (2gx + 1) (2gy + 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.

To download the report in PDF format click here: USC-SIPI-164.pdf (0.8Mb)