Superlinear convergence for PCG using band plus algebra preconditioners for Toeplitz systems

The paper studies fast and efficient solution algorithms for n x n symmetric ill conditioned Toeplitz systems T-n(f)x = b where the generating function f is known a priori, real valued, nonnegative, and has isolated roots of even order. The preconditioner that we propose is a product of a band Toeplitz matrix and matrices that belong to a certain trigonometric algebra. The basic idea behind the proposed scheme is to combine the advantages of all components of the product that are well known when every component is used as a stand-alone preconditioner. As a result we obtain a flexible preconditioner which can be applied to the system T-n(f)x = b infusing superlinear convergence to the PCG method. The important feature of the proposed technique is that it can be extended to cover the 2D case, i.e. ill-conditioned block Toeplitz matrices with Toeplitz blocks. We perform many numerical experiments, whose results confirm the theoretical analysis and effectiveness of the proposed strategy. (c) 2008 Elsevier Ltd. All rights reserved.