Toeplitz preconditioners constructed from linear approximation processes

Preconditioned conjugate gradients (PCG) are widely and successfully used m ethods to solve Toeplitz linear systems A(n)(f)x = b: Here we consider prec onditioners belonging to trigonometric matrix algebras and to the band Toep litz 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 pr ove that the necessary (and sufficient) condition, in order to devise a sup erlinear PCG method, is that the spectrum of the preconditioners is describ ed by a sequence of approximation operators "converging" to f. The other im portant 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 onl y class of methods for which we may obtain impressive evidence of superline ar convergence behavior is the one [S. Serra, Math. Comp., 66 (1997), pp. 6 51-665] based on band Toeplitz matrices with weakly increasing bandwidth.