Toeplitz preconditioners for Hermitian Toeplitz systems

We propose a new type of preconditioners for Hermitian positive definite Toeplitz systems A_nx = 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 Ã_nA_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_nA_n will have clustered spectra around 1.