New PCG based algorithms for the solution of Hermitian Toeplitz systems

In order to solve Toeplitz linear systems An(f)x=b generated by a nonnegative integrable function f, through use of the preconditioned conjugate gradient (PCG) method, several authors have proposed An(g) as preconditioner in the case where g is a trigonometric polynomial [10, 14, 27, 12, 28]. In preceding works, we studied the distribution and the extremal properties of the spectrum of the preconditioned matrix G=A n -1 (g) An(f). In this paper we prove that the union of the spectra of all the Gn is dense on the essential range of f/g, i.e., ER(f/g) and we obtain asymptotic information about the rate of convergence of the smallest eigenvalue λ l n of Gn to r (and of λ n n to R). As a consequence of this second order result, it is possible to handle the case where f has zeros of any order θ, through the PCG methods proposed in [10, 14]. This is a noteworthy extension since the techniques developed in [10, 14, 27, 12, 28] are shown to be effective only when f has zeros of even orders. The cost of this procedure is O(n1+c(θ) log n) arithmetic operations (ops) where the quantity c(θ) belongs to interval [0,2-1] and takes the maximum value 2-1 when f has a zero of odd order. Finally, for the special case of zeros of odd orders, we propose a further algorithm which makes use of the PCG techniques proposed in [10, 14, 27, 12, 28] for the even order case, reducing the cost to O(n long n) ops.