Inverse Toeplitz preconditioners for Hermitian Toeplitz systems

Abstract

In this paper we consider solving Hermitian Toeplitz systems T nx = b by using the preconditioned conjugate gradient (PCG) method. Here the Toeplitz matrices Tn are assumed to be generated by a non-negative continuous 2π-periodic function f, i.e. Tn = script J sign[f]. It was proved in (Linear Algebra Appl. 1993; 190:181) that if f is positive then the spectrum of script J signn[1/f]script J sign n[f] is clustered around 1. We prove that the trigonometric polynomial qn (s) (s ≥ 2, cf. (2) and (3)) converges to 1/f uniformly as n → ∞ under the condition that 1/f is in Wiener class. It follows that the computational cost of the PCG method can be reduced by replacing 1/f with qN (2) where N < n. We also extend our method to construct efficient preconditioners for Tn when f has finite zeros of even orders. We prove that with our preconditioners, the preconditioned matrix has spectrum clustered around 1. It follows that the PCG methods converge very fast when applied to solve the preconditioned systems. Numerical results are given to demonstrate the efficiency of our preconditioners. Copyright © 2004 John Wiley & Sons, Ltd.