A numerical study of acceleration schemes for restarted minimum residual methods

Oliver Ernst, Michael Eiermann and Olaf Schneider

Institut fuer Angewandte Mathematik II
TU Bergakademie Freiberg
09596 Freiberg, Germany


Abstract

The two main approaches for solving non-Hermitian linear systems of equations with Krylov subspace methods differ in the schemes used to generate suitable basis vectors for computing corrections to the approximate solution. In the early 90s, the introduction of look-ahead techniques to stabilize the Lanczos process along with the QMR method made biorthogonalization methods an attractive approach due to their (for all practical purposes) linear cost in storage and arithmetic. Moreover, these methods, even if used without look-ahead techniques, often outperform those based on orthogonalisation such as GMRES, which constitute the second main approach. This is because methods of the latter class must be restarted or truncated in order to make their application feasible. Recently a number of acceleration techniques have been proposed which attempt to compensate for the effects of restarting and truncation, thus closing the gap between orthogonalisation and biorthogonalisation methods. In this work we complement our recent analysis [1] of three of the more popular of these acceleration schemes with a careful numerical study which attempts to identify the strengths and weaknesses of each scheme.

[1] M. Eiermann, O.G. Ernst and O. Schneider. Analysis of acceleration strategies for restarted minimal residual methods. J. Comp. Appl. Math 123 (2000) pp. 262--292.