CIRCULANT PRECONDITIONERS FOR HERMITIAN TOEPLITZ SYSTEMS

The solutions of Hermitian positive definite Toeplitz systems Ax = b by the preconditioned conjugate gradient method for three families of circulant preconditioners C is studied. The convergence rates of these iterative methods depend on the spectrum of C^-1A. For a Toeplitz matrix A with entries that are Fourier coefficients of a positive function f in the Wiener class, the invertibility of C is established, as well as that the spectrum of the preconditioned matrix C^-1A clusters around one. It is proved that if f is (l  + 1)-times differentiable, with l > 0, then the error after 2_q conjugate gradient steps will decrease like ((q - 1)!)^-2l. It is also shown that if C copies the central diagonals of A, then C minimizes ǁC - Aǁ₁ and ǁC - Aǁ_∞.