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 A(n,m)x = b, where A(n,m) is an n x n positive definite block Toeplitz matrix with m x m Toeplitz blocks. In particular we propose a sparse preconditioner P-n,P-m such that the condition number of the preconditioned matrix turns out to be less than a suitable constant independent of both n and pn, even if the condition number of A(n,m) tends to infinity. 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.