## Abstract

The solution of n-by-n complex Toeplitz systems ** A_{n}x** =

**by the preconditioned conjugate gradient method is studied. The preconditioner**

*b***is the circulant matrix that minimizes ||**

*C*_{n}**||**

*B*_{n}-A_{n}_{F}over all circulant matrices

**. The authors prove that if the generating function of**

*B*_{n}**is a**

*A*_{n}**2μ**-periodic continuous complex-valued function without any zeros, then the spectrum of the normalized preconditioned matrix

**(C**will be clustered around one. Hence they show that if the condition number of

_{n}^{-1}A_{n})*(C_{n}^{-1}A_{n})**A**is of

_{n}

**, the conjugate gradient method, when applied to solving the normalized preconditioned system, converges in at most**

*O*(*n*^{α})**steps. Thus the total complexity of the algorithm is**

*O*(α log n+1)**.**

*O*(*αn*log^{2}*n*+ 1 log*n*)Original language | English |
---|---|

Pages (from-to) | 1193-1207 |

Number of pages | 15 |

Journal | SIAM Journal on Numerical Analysis |

Volume | 30 |

Issue number | 4 |

DOIs | |

Publication status | Published - Aug 1993 |

Externally published | Yes |

## Keywords

- Toeplitz matrix
- circulant matrix
- preconditioned conjugate gradient method
- generating function