Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems

In this paper we are concerned with the solution of $n\times n$ Hermitian Toeplitz systems with nonnegative generating functions $f$. The preconditioned conjugate gradient (PCG) method with the well-known circulant preconditioners fails in the case where $f$ has zeros. In this paper we consider as preconditioners band-Toeplitz matrices generated by trigonometric polynomials $g$ of fixed degree $l$. We use different strategies of approximation of $f$ to devise a polynomial $g$ which has some analytical properties of $f$, is easily computable and is such that the corresponding preconditioned system has a condition number bounded by a constant independent of $n$. For each strategy we analyze the cost per iteration and the number of iterations required for the convergence within a preassigned accuracy. We obtain different estimates of $l$ for which the total cost of the proposed PCG methods is optimal and the related rates of convergence are superlinear. Finally, for the most economical strategy, we perform various numerical experiments which fully confirm the effectiveness of approximation theory tools in the solution of this kind of linear algebra problems.