Circulant preconditioners for toeplitz matrices with piecewise continuous generating functions

We consider the solution of -by- Toeplitz systems T„x = b by preconditioned conjugate gradient methods. The preconditioner Cn is the T. Chan circulant preconditioner, which is defined to be the circulant matrix that minimizes B„ - T„fover all circulant matrices B„ . For Toeplitz matrices generated by positive In -periodic continuous functions, we have shown earlier that the spectrum of the preconditioned system C„Tn 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 e sufficiently small, there are 0(log) eigenvalues of Cñ ’ T„ that lie outside the interval (1 —e , 1 + e). In particular, the spectrum of Cñ ’ Tn cannot be clustered around 1. Numerical examples are given to verify that the convergence rate of the method is no longer superlinear in general.