A classification scheme for regularizing preconditioners, with application to Toeplitz systems

Preconditioning techniques for linear systems are widely used in order to speed up the convergence of iterative methods. If the linear system is generated by the discretization of an ill-posed problem, preconditioning may lead to wrong results, since components related to noise on input data are amplified. Using basic concepts from the theory of inverse problems, we identify a class of preconditioners which acts as a regularizing tool. In this paper we study relationships between this class and previously known circulant preconditioners for ill-conditioned Hermitian Toeplitz systems. In particular, we deal with the low-pass filtered optimal preconditioners and with a recent family of superoptimal preconditioners. We go on to describe a set of preconditioners endowed with particular regularization properties, whose effectiveness is supported by several numerical tests. © 2004 Elsevier Inc. All rights reserved.