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^{ - 1} A$. 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^{ - 1} A$ clusters around one. It is proved that if f is $(l + 1)$-times differentiable, with $l > 0$, then the error after $2q$ 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 \|_1 $ and $\| C - A \|_\infty $.