The Spectra of Super-Optimal Circulant Preconditioned Toeplitz Systems

The solutions of Hermitian positive-definite Toeplitz systems A_nx = b by the preconditioned conjugate gradient method are studied. The preconditioner, called the 'super-optimal' preconditioner, is the circulant matrix T_n that minimizes ∥I - C_n^-1 A_n∥_F over all circulant matrices C_n. The convergence rate is known to be governed by the distribution of the eigenvalues of T_n^-1 A_n. For n-by-n Toeplitz matrix A_n with entries being Fourier coefficients of a positive function in the Wiener class, the asymptotic behaviour of the eigenvalues of the preconditioned matrix T_n^-1 A_n is found as n increases, and it is proved that they are clustered around one.