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

“Spectral Properties of Preconditioned Rational Toeplitz Matrices: The Nonsymmetric Case”

by Ta-Kang Ku and C.-C. Jay Kuo

April 1991

Various preconditioners for symmetric positive-definite (SPD) Toeplitz matrices in circulant matrix form have recently been proposed. The spectral properties of the preconditioned PSD Toeplitz matrices have also been studied. In this research, we apply Strang's preconditioner SN and our preconditioner KN to an N x N nonsymmetric (or nonhermitian) Toeplitz system TNx=b. For a large class of Toeplitz matrices, we prove that the singular values of SN-1TN and KN-1TN are clustered around unity except a fixed number independent of N. If TN is additionally generated by a rational function, we are able to characterize the eigenvalues of SN-1TN and KN-1TN directly. Let the eigenvalues of SN-1TN and KN-1TN be classified into the outliers and the clustered eigenvalues depending on whether they converge to 1 asymptotically. Then, the number of outliers depends on the order of the rational generating function, and the clustering radius is proportional to the magnitude of the last elements in the generating sequence used to construct the preconditioner. Numerical experiments are provided to illustrate our theoretical study.

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