Deflation and Restarting in Krylov Methods
Techniques to control memory and rescue convergence in Krylov solvers by recycling or removing troublesome subspace directions.
The memory problem in GMRES
GMRES stores the full orthonormal basis of the growing Krylov subspace, so its memory and orthogonalization cost climb with each iteration. On hard problems that need many iterations, this becomes prohibitive. The standard remedy is restarting: after m iterations, discard the basis and begin afresh using the current approximation as the new starting point. This caps memory at m vectors.
The cost of restarting
Restarting throws away the accumulated subspace, and with it information the method had built up about the problem. This can stall convergence, especially when a few small eigenvalues govern the slow modes: restarted GMRES repeatedly rediscovers and loses the same directions, sometimes converging far slower than the full method or not at all. Deflation is the cure.
Deflation
Deflation identifies the troublesome directions, typically the eigenvectors of the smallest eigenvalues that slow convergence, and removes their influence. It either projects them out of the operator (making the solver see a problem with a better-clustered spectrum) or preserves them across restarts so they are not rediscovered each cycle. Effectively, deflation treats the few worst modes directly and lets the Krylov method handle the rest.
- Restarting: cap memory by periodically discarding the subspace
- Deflated restarting (GMRES-DR): retain approximate eigenvectors across restarts
- Subspace recycling: reuse subspace information across a sequence of related systems
- Augmentation: add fixed useful vectors to the search space
Recycling for sequences of systems
Many applications solve a sequence of closely related linear systems, for instance the Newton steps of a Newton-Krylov solver or successive time steps. Recycling Krylov methods carry a useful subspace from one solve to the next, so each new system starts with information already gathered, cutting the iterations needed. These techniques make GMRES practical on the stiff, repeatedly-solved systems common in implicit simulation.