13 - Preconditioning

Summary

Introduction

As we have seen in our discussions on the various Krylov subspace methods, they are not robust in the sense that they can be guaranteed to lead to acceptable approximate solutions within modest computing time and storage (modest with respect to alternative solution methods). For some methods (for instance, full GMRES) it is obvious that they lead, in exact arithmetic, to the exact solution in maximal n iterations, but that may not be very practical. Other methods are restricted to specific classes of problems (CG, MINRES) or suffer from such nasty side-effects as stagnation or breakdown (Bi-CG, Bi-CGSTAB). Such poor convergence depends in a very complicated way on spectral properties (eigenvalue distribution, field of values, condition of the eigensystem, etc.) and this information is not available in practical situations.

The trick is then to try to find some nearby operator K such that K⁻¹A has better (but still unknown) spectral properties. This is based on the observation that for K = A, we would have the ideal system K⁻¹Ax = I x = K⁻¹b and all subspace methods would deliver the true solution in one singe step. The hope is that for K in some sense close to A a properly selected Krylov method applied to, for instance, K⁻¹Ax = K⁻¹b, would need only a few iterations to yield a good enough approximation for the solution of the given system Ax = b. An operator that is used for this purpose is called a preconditioner for the matrix A.