New Band Toeplitz Preconditioners for Ill-Conditioned Symmetric Positive Definite Toeplitz Systems

Abstract

It is well known that preconditioned conjugate gradient (PCG) methods are widely used to solve ill-conditioned Toeplitz linear systems Tn(f)x=b. In this paper we present a new preconditioning technique for the solution of symmetric Toeplitz systems generated by nonnegative functions f with zeros of even order. More specifically, f is divided by the appropriate trigonometric polynomial g of the smallest degree, with zeros the zeros of f to eliminate its zeros. Using rational approximation we approximate $\sqrt{f/g}$ by $\frac{p}{q}$, $p,q$ trigonometric polynomials and consider $\frac{p^2g}{q^2}$ as a very satisfactory approximation of f. We propose the matrix $M_n=B^{-1}_n(q)B_n(p^2g)B^{-1}_n(q)$, where $B(\cdot)$ denotes the associated band Toeplitz matrix, as a preconditioner whence a good clustering of the spectrum of its preconditioned matrix is obtained. We also show that the proposed technique can be very flexible, a fact that is confirmed by various numerical experiments so that in many cases it constitutes a much more efficient strategy than the existing ones.