Extending Nested Krylov Subspace Methods

Serge Goossens

Serge Goossens
Department of Computer Science
Celestijnenlaan 200A
B-3001 Heverlee


For most non-Hermitian problems one cannot expect to find a short recurrence that generates the optimal approximations from successive Krylov subspaces. This implies that either short recurrences are used at the cost of optimality or optimality is kept at the cost of high storage demands. In practice restarted or truncated versions of optimal methods are often used.

Recently two nested Krylov methods, GMRESR (= GCR/GMRES) and FGMRES/GMRES, have been proposed. Both FGMRES and GCR allow the use of a preconditioner that can be different in every iteration, as e.g. GMRES. The convergence behaviour in these methods is roughly the same. Their objective is to compute near-optimal approximations by only storing a few but well-chosen vectors.

The above schemes can be improved by observing that the right-hand side in the inner iteration is orthogonal with respect to some subspace generated in the outer iteration. This orthogonality property can be taken into account in the inner iteration. This observation has already been exploited in the GCRO method. We present Extended GMRES, a preconditioning technique for FGMRES, which can be compared to GCRO in the same way as FGMRES/GMRES can be compared to GMRESR. An analysis of this new method is given.

For a similar number of matrix-vector multiplications, these new methods always yield a solution which is at least as accurate as the one obtained in the absence of the additional orthogonalisations.

In terms of CPU time, the methods with the additional orthogonalisations slow down as the number of outer iterations increases. This is due to the cost of the additional orthogonalisations which increases with the number of vectors kept in the outer iteration. Therefore, it is only advantageous to perform the additional orthogonalisations in the first few steps of the outer iteration, when the overhead is small. The effect of the additional orthogonalisations is predictable and the gain in residual norm reduction can be estimated. Hence dynamic switching criteria are established for deciding when to stop performing the additional orthogonalisations.

Due to the additional orthogonalisations breakdown may occur. This has been observed in GCRO where a singular operator is used to construct a Krylov subspace in the inner iteration.

A straightforward approach to avoid breakdown is to use the LSQR switch, which always leads to a decrease of the residual norm. This is essentially one step of an algorithm based on the normal equations. It is well known that the normal equations can be ill-conditioned and that methods based on the normal equations often converge slowly. In general one tries to avoid the use of the normal equations, i.e. the use of the transpose of the matrix. We show that the combination of FGMRES and GMRESR allows the construction of a transpose-free cure for breakdown.

Finally, we will comment on truncation strategies for optimal Krylov subspace methods and an implicitly restarted FGMRES algorithm for the outer iteration.