## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 701-718 |

Number of pages | 18 |

Journal | Mathematics of Computation |

Volume | 61 |

Issue number | 204 |

DOIs | |

Publication status | Published - Oct 1993 |

Externally published | Yes |

## Keywords

- Circulant matrix
- Generating function
- Preconditioned conjugate gradient method
- Superlinear convergence rate
- Toeplitz matrix