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

The paper studies fast and efficient solution algorithms for n×nn×n symmetric ill conditioned Toeplitz systems Tn(f)x=bTn(f)x=b where the generating function ff 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 Tn(f)x=bTn(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 2D2D 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.