On the sensitivity of some spectral preconditioners

It is well known that the convergence of the conjugate gradient method for solving symmetric positive definite linear systems depends to a large extent on the eigenvalue distribution. In many cases, it is observed that “removing ” the extreme eigenvalues can greatly improve the convergence. Several preconditioning techniques based on approximate eigenelements have been proposed in the past few years that attempt to tackle this problem. The proposed approaches can be split into two main families depending on whether the extreme eigenvalues are moved exactly to one or are shift to close to one. The first technique is often referred to the deflating approach, while the latter is referred to as coarse grid preconditioner by analogy to techniques first used in domain decomposition methods. Many variants exist in the two families that reduce to the same preconditioners if the exact eigenelements are used. In this paper we investigate the behaviour of some of these techniques when the eigenelements are only known approximately. We use the perturbation theory for eigenvalues and eigenvectors to investigate the behaviour of the spectrum of the preconditioned systems using first order approximation. We illustrate the sharpness of the first order approximation and show the effect of the inexactness of the eigenelements on the behaviour of the resulting preconditioner when applied to accelerate the conjugate gradient method.