Circulant preconditioners for Toeplitz matrices with piecewise continuous generating functions

Abstract:

We consider the solution of n-by-n Toeplitz systems ${T_n}x = b$ by preconditioned conjugate gradient methods. The preconditioner ${C_n}$ is the T. Chan circulant preconditioner, which is defined to be the circulant matrix that minimizes ${\left \| {{B_n} - {T_n}} \right \|_F}$ over all circulant matrices ${B_n}$. For Toeplitz matrices generated by positive $2\pi$-periodic continuous functions, we have shown earlier that the spectrum of the preconditioned system $C_n^{ - 1}{T_n}$ is clustered around 1 and hence the convergence rate of the preconditioned system is superlinear. However, in this paper, we show that if instead the generating function is only piecewise continuous, then for all $\varepsilon$ sufficiently small, there are $O(\log n)$ eigenvalues of $C_n^{ - 1}{T_n}$ that lie outside the interval $(1 - \varepsilon ,1 + \varepsilon )$. In particular, the spectrum of $C_n^{ - 1}{T_n}$ cannot be clustered around 1. Numerical examples are given to verify that the convergence rate of the method is no longer superlinear in general.