SPECTRAL PROPERTIES OF PRECONDITIONED RATIONAL TOEPLITZ MATRICES

Various Toeplitz preconditioners P(N) have recently been proposed so that an N x N symmetric positive definite Toeplitz system T(N) x = b can be solved effectively by the preconditioned conjugate gradient (PCG) method. It has been proven that if T(N) is generated by a positive function in the Wiener class, the eigenvalues of the preconditioned matrices P(N)-1T(N) are clustered between (1 - epsilon, 1 + epsilon) except for a fixed number independent of N. In this research, the spectra of P(N)-1T(N) are characterized more precisely for rational Toeplitz matrices T(N) with preconditioners proposed by Strang [Stud. Appl. Math., 74 (1986), pp. 171-176] and Ku and Kuo [IEEE Trans. Signal Process., 40 (1992), pp. 129-141]. The eigenvalues of P(N)-1T(N) are classified into two classes, i.e., the outliers and the clustered eigenvalues, depending on whether they converge to 1 asymptotically. It is proved that the number of outliers depends on the order of the rational generating function, and the clustering radius epsilon is proportional to the magnitude of the last element in the generating sequence used to construct these preconditioners. For the special case with T(N) generated by a geometric sequence, this approach can be used to determine the exact eigenvalue distribution of P(N)-1T(N) analytically.