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^-1_n 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^-1_n 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^-1_n A_n is found as n increases, and it is proved that they are clustered around one.