Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems

A particular class of preconditioners for the conjugate gradient method and other iterative methods is proposed for the solution of linear systems An,mx=b, where An,m is an n×n positive definite block Toeplitz matrix with m×m Toeplitz blocks. In particular we propose a sparse preconditioner Pn,m such that the condition number of the preconditioned matrix turns out to be less than a suitable constant independent of both n and m, even if the condition number of An,m tends to ∞. This leads to iterative methods which require a number of steps independent of m and n in order to reduce the error by a given factor.