The Spectrum of a Family of Circulant Preconditioned Toeplitz Systems

The solutions of symmetric positive definite Toeplitz systems Ax = b are studied by the preconditioned conjugate gradient method. The preconditioner is the circulant matrix C that minimizes the Frobenius norm ‖C - A‖_F [T. Chan, “An Optimal Circulant Preconditioner for Toeplitz Systems,” UCLA Department of Mathematics, CAM Report 87-06, June 1987]. The convergence rate of these iterative methods is known to depend on the distribution of the eigenvalues of C^-1A. For Toeplitz matrix A with entries which are Fourier coefficients of a positive function in the Wiener class, this paper establishes the invertibility of C, finds the asymptotic behaviour of the eigenvalues of the preconditioned matrix C^-1A as the dimension increases and proves that they are clustered around 1.