New GMRES(k) algorithms with explicit restarts and the analysis of their properties based on matrix relations in QR form

S. A. Kharchenko ; A. Yu. Yeremin

Zapiski Nauchnykh Seminarov POMI, Computational methods and algorithms. Part XIV, Tome 268 (2000), pp. 190-241

Résumé

The paper considers the problem of constructing a basic iterative scheme for solving systems of linear algebraic equations with unsymmetric and indefinite coefficient matrices. A new GMRES-type algorithm with explicit restarts is suggested. When restarting, this algorithm takes into account the spectral/singular data carried on by orthogonal matrix relations in the so-called QR form, which arise when performing inner iterations of Arnoldi type. The main idea of the algorithm developed is to organize inner iterations and the filtering of directions before restarting in such a way that, from a restart to another, matrix relations effectively accumulate information concerning the current approximate solution and, simultaneously, spectral/singular data, which allow the algorithm to converge with a rate comparable with that of the GMRES algorithm without restarts. Convergence theory is provided for the case of nonsingular, unsymmetric, and indefinite matrices. A bound for the rate of decrease of residual in the course of inner Arnoldi-type iterations is obtained. This bound depends on a spectral/singular characterization of the subspace spanned by the directions retained upon filtering and is used in developing efficient filtering procedures.