Circulant preconditioners for Toeplitz matrices with piecewise continuous generating functions

We consider the solution of n-by-n Toeplitz systems T_nx = 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 ||Bn - Tn||_F  over all circulant matrices Bn. For Toeplitz matrices generated by positive 2π-periodic continuous functions, we have shown earlier that the spectrum of the preconditioned system C_n^-1T_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 ε sufficiently small, there are O (log n) eigenvalues of C_n^-1T_n that lie outside the interval (1 - ε , 1 + ε) . In particular, the spectrum of C_n^-1T_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.