TOEPLITZ PRECONDITIONERS FOR HERMITIAN TOEPLITZ-SYSTEMS

We propose a new type of preconditioners for Hermitian positive defini te Toeplitz systems A(n)x = b where A(n) are assumed to be generated b y functions f that are positive and 2pi-periodic. Our approach is to p recondition A(n) by the Toeplitz matrix A(n) generated by 1/f. We prov e that the resulting preconditioned matrix A(n)A(n) will have clustere d spectrum. When A(n) cannot be formed efficiently, we use quadrature rules and convolution products to construct nearby approximations to A (n). We show that the resulting approximations are Toeplitz matrices w hich can be written as sums of {omega}-circulant matrices. As a side r esult, we prove that any Toeplitz matrix can be written as a sum of {o mega}-circulant matrices. We then show that our Toeplitz preconditione rs T(n) are generalizations of circulant preconditioners and the way t hey are constructed is similar to the approach used in the additive Sc hwarz method for elliptic problems. We finally prove that the precondi tioned systems T(n)A(n) will have clustered spectra around 1.