## Abstract

We propose a new type of preconditioners for Hermitian positive definite Toeplitz systems A_{n}x = b where A_{n} are assumed to be generated by functions f that are positive and 2π-periodic. Our approach is to precondition Ã_{n} by the Toeplitz matrix Ã_{n} generated by 1/f. We prove that the resulting preconditioned matrix Ã_{n}A_{n} will have clustered spectrum. When Ã_{n} cannot be formed efficiently, we use quadrature rules and convolution products to construct nearby approximations to Ã_{n}. We show that the resulting approximations are Toeplitz matrices which can be written as sums of {ω}-circulant matrices. As a side result, we prove that any Toeplitz matrix can be written as a sum of {ω}-circulant matrices. We then show that our Toeplitz preconditioners T_{n} are generalizations of circulant preconditioners and the way they are constructed is similar to the approach used in the additive Schwarz method for elliptic problems. We finally prove that the preconditioned systems T_{n}A_{n} will have clustered spectra around 1.

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

Pages (from-to) | 181-208 |

Number of pages | 28 |

Journal | Linear Algebra and Its Applications |

Volume | 190 |

DOIs | |

Publication status | Published - 1 Sept 1993 |

Externally published | Yes |