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-163

“Spectral Properties of Preconditioned Rational Toeplitz Matrices”

by Takang Ku and C.-C. Jay Kuo

September 1990

Various Toeplitz preconditioners PN have recently been proposed so that the N C N symmetric positive definite Toeplitz system TN x = b can be solved effectively by the preconditioned conjugate gradient (PCG) method. It was proved that, if TN is generated by a positive function in the Wiener class, the spectra of the preconditioned matrices PN-1TN are clustered between (1 - e, 1 + e) except a finite number of outliers. In this research, we characterize the spectra of PN-1TN more precisely for rational Toeplitz matrices TN with preconditioners proposed by Strang [19] and the authors [15]. We prove that the number of outliers depends on the order of the rational generating function, and the clustering radius v is proportional to the magnitude of the last element in the generating sequence used to construct these preconditioners. For the special case with TN generated by a geometric sequence, our approach can be used to determine the exact eigenvalue distribution of PN-1TN analytically.

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