A Class of Spectral Two-Level Preconditioners

Abstract

It is well known that the convergence of Krylov methods for solving the linear system often depends to a large extent on the eigenvalue distribution. In many cases, it is observed that ``removing' the smallest eigenvalues can greatly improve the convergence. Several techniques 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 scheme enlarges the generated Krylov space or adaptively updates the preconditioner. In this paper, we follow the second approach and propose a class of preconditioners both for unsymmetric and for symmetric linear systems that can also be adapted for symmetric positive definite problems. We effectively solve the preconditioned system exactly in the low dimensional space associated with the smallest eigenvalues and use this to update the preconditioned residual. This update results in shifting eigenvalues from close to the origin to near to one for the new preconditioner. This is ideal when there are only a few eigenvalues near the origin while all the others are close to one because the updated preconditioned system becomes close to the identity. We illustrate the performance of our method through extensive numerical experiments on a set of general linear systems. Finally, we show the advantages of the preconditioners for solving dense linear systems arising in electromagnetism applications, which were the main motivation for this work.