Toeplitz preconditioners for Hermitian Toeplitz systems

Abstract

We propose a new type of preconditioners for Hermitian positive definite Toeplitz systems Anx = b where An 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 ÃnAn 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 Tn 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 TnAn will have clustered spectra around 1. © 1993.