Preconditioners for Sparse Iterative Methods

Iterative methods for solving sparse systems of linear equations are potentially less memory and computation intensive than direct methods, but often experience slow convergence or fail to converge at all. The robustness and the speed of Krylov subspace iterative methods is improved, often dramatically, by preconditioning. Preconditioning is a technique for transforming the original system of equations into one with an improved distribution (clustering) of eigenvalues so that the transformed system can be solved in fewer iterations. A key step in preconditioning a linear system is to find a nonsingular preconditioner matrix such that the inverse of is as close to the inverse of as possible and solving is significantly less expensive than solving . The system is then solved by solving . This particular example shows what is known as left preconditioning. There are two other formulations, known as right preconditioning and split preconditioning; the basic concept, however, is the same. Other practical requirements for successful preconditioning are that the cost of computing itself must be low and the memory required to compute and apply must be significantly less than that for solving via direct factorization.