TOEPLITZ EQUATIONS BY CONJUGATE GRADIENTS WITH CIRCULANT PRECONDITIONER

This paper studies the solution of symmetric positive definite Toeplitz systems Ax = b by the preconditioned conjugate gradient method. The preconditioner is a circulant matrix C that copies the middle diagonals of A, and each iteration uses the Fast Fourier Transform. Convergence is governed by the eigenvalues of C^-1 A-a Toeplitz-circulant eigenvalue problem-and it is fast if those eigenvalues are clustered. The limiting behavior of the eigenvalues is found as the dimension increases, and it is proved that they cluster around ℷ = 1. For a wide class of problems the error after q conjugate gradient steps decreases as r^q2.