Minimum residual methods for augmented systems

B. Fischer, A. Ramage, D. J. Silvester, A. J. Wathen

Research output: Contribution to journalArticle

151 Citations (Scopus)

Abstract

For large systems of linear equations, iterative methods provide attractive solution techniques. We describe the applicability and convergence of iterative methods of Krylov subspace type for an important class of symmetric and indefinite matrix problems, namely augmented (or KKT) systems. Specifically, we consider preconditioned minimum residual methods and discuss indefinite versus positive definite preconditioning. For a natural choice of starting vector we prove that when the definite and indefinite preconditioners are related in the obvious way, MINRES (which is applicable in the case of positive definite preconditioning) and full GMRES (which is applicable in the case of indefinite preconditioning) give residual vectors with identical Euclidean norm at each iteration. Moreover, we show that the convergence of both methods is related to a system of normal equations for which the LSQR algorithm can be employed. As a side result, we give a rare example of a non-trivial normal(1) matrix where the corresponding inner product is explicitly known: a conjugate gradient method therefore exists and can be employed in this case.

Original languageEnglish
Pages (from-to)527-543
Number of pages17
JournalBIT Numerical Mathematics
Volume38
Issue number3
DOIs
Publication statusPublished - 1 Sep 1998

    Fingerprint

Keywords

  • conjugate gradients
  • indefinite systems
  • minimum residual methods
  • preconditioners

Cite this