## Abstract

We study the solutions of Toeplitz systems A_{n}x=b by the preconditioned conjugate gradient method. The n ×n matrix A_{n} is of the form a_{0}I+H_{n} where a_{0} is a real number, I is the identity matrix and H_{n} is a skew-Hermitian Toeplitz matrix. Such matrices often appear in solving discretized hyperbolic differential equations. The preconditioners we considered here are the circulant matrix C_{n} and the skew-circulant matrix S_{n} where A_{n}=1/2(C_{n}+S_{n}). The convergence rate of the iterative method depends on the distribution of the singular values of the matrices C^{-1}_{n} A_{n} and S^{-1}_{n}A_{n}. For Toeplitz matrices A_{n} with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility of C_{n} and S_{n} and prove that the singular values of C^{-1}_{n}A_{n} and S^{-1}_{n}A_{n} are clustered around 1 for large n. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.

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

Pages (from-to) | 632-646 |

Number of pages | 15 |

Journal | BIT |

Volume | 31 |

Issue number | 4 |

DOIs | |

Publication status | Published - Dec 1991 |

Externally published | Yes |

## Keywords

- circulant matrix
- preconditioned conjugate gradient method
- skew-circulant matrix
- Skew-Hermitian type Toeplitz matrix