Toeplitz preconditioners constructed from linear approximation processes

Preconditioned conjugate gradients (PCG) are widely and successfully used methods to solve Toeplitz linear systems A(n)(f)x = b: Here we consider preconditioners belonging to trigonometric matrix algebras and to the band Toeplitz class and we analyze them from the viewpoint of the function theory in the case where f is supposed continuous and strictly positive. First we prove that the necessary (and sufficient) condition, in order to devise a superlinear PCG method, is that the spectrum of the preconditioners is described by a sequence of approximation operators "converging" to f. The other important information we deduce is that while the matrix algebra approach is substantially not sensitive to the approximation features of the underlying approximation operators, the band Toeplitz approach is. Therefore, the only class of methods for which we may obtain impressive evidence of superlinear convergence behavior is the one [S. Serra, Math. Comp., 66 (1997), pp. 651-665] based on band Toeplitz matrices with weakly increasing bandwidth.