QMR: A quasi-minimal residual method for non-Hermitian linear systems
type: Item
instance of: scholarly article
title: QMR: A quasi-minimal residual method for non-Hermitian linear systems
zbMATH Open document ID: 0754.65034
DOI: 10.1007/BF01385726
author: Noël M. Nachtigal
author: Roland W. Freund
published in: Numerische Mathematik
publication date: 1992-06-27T00:00:00Z
full work available at URL: https://eudml.org/doc/133596
review text: The basic Lanczos biorthogonal method [cf. \textit{C. Lanczos}, J. Res. Natl. Bur. Stand. 49, 33-53 (1952; MR 14.501)] for the solution of the linear system \(Ax=b\), \(A\) non-Hermitian, generates sequences \(\{v_ 1,v_ 2,\dots,v_ n\}\) and \(\{w_ 1,w_ 2,\dots,w_ n\}\), \(n=1,2,\dots,\) from: \(v_{j+1}=Av_ j-\alpha_ jv_ j-\beta_ jv_{j-1}\) and \(w_{j+1}=A^ Tv_ j-\alpha_ j w_ j-\gamma_ jw_{j-1}\) where the scalar coefficients are chosen to satisfy the biorthogonality condition \(w^ T_ kv_ l=d_ k\delta_{kl}\). The biconjugate gradient (BCG) method is a variant of the Lanczos' method. Note that if \(w^ T_{n+1}v_{n+1}=0\), the above process must be terminated to prevent division by zero at the next step. So-called look- ahead variants of BCG attempt to overcome this difficulty [cf \textit{B. N. Parlett}, \textit{D. R. Taylor}, \textit{Z. A. Liu}, Math. Comput. 44, 105-124 (1985; Zbl 0564.65022)]. This paper presents the quasi-minimal residual (QMR) approach, a generalization of BCG which overcomes the tendency to numerical instability. It incorporates the \(n\)th iteration of the look-ahead BCG, starting with \(v_ 1=r_ 0/\| r_ 0\|\), where \(r_ 0\) is the residual \(r_ 0=b-Ax_ 0\) of \(x_ 0\), an initial guess to the solution of the linear system. Implementation details are presented, together with further properties and an error bound. In conclusion, results of extensive numerical experiments with QMR and other iterative methods mentioned in the paper are presented.
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 65N22
zbMATH DE Number: 29619
zbMATH Keywords: non-Hermitian linear systems
zbMATH Keywords: sparse linear systems
zbMATH Keywords: quasi-minimal residual method
zbMATH Keywords: Lanczos biorthogonal method
zbMATH Keywords: numerical instability
zbMATH Keywords: error bound
zbMATH Keywords: numerical experiments
zbMATH Keywords: iterative methods
zbMATH Keywords: biconjugate gradient method
reviewed by: Adrian Swift
describes a project that uses: ITSOL
describes a project that uses: SPARSKIT
describes a project that uses: CGS
describes a project that uses: Harwell-Boeing sparse matrix collection
MaRDI profile type: Publication
cites work: Sparse matrix test problems
cites work: Necessary and Sufficient Conditions for the Existence of a Conjugate Gradient Method
cites work: On the constrained Chebyshev approximation problem on ellipses
cites work: An Implementation of the Look-Ahead Lanczos Algorithm for Non-Hermitian Matrices
cites work: Q5185900
cites work: Methods of conjugate gradients for solving linear systems
cites work: The Tchebychev iteration for nonsymmetric linear systems
cites work: An Iterative Solution Method for Linear Systems of Which the Coefficient Matrix is a Symmetric M-Matrix
cites work: Solution of Sparse Indefinite Systems of Linear Equations
cites work: Reduction to Tridiagonal Form and Minimal Realizations
cites work: A Look-Ahead Lanczos Algorithm for Unsymmetric Matrices
cites work: The Lanczos Biorthogonalization Algorithm and Other Oblique Projection Methods for Solving Large Unsymmetric Systems
cites work: GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
cites work: CGS, A Fast Lanczos-Type Solver for Nonsymmetric Linear systems
cites work: Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems
cites work: Q5674306
Recommended article: Q4035550
Recommended article: A Transpose-Free Quasi-Minimal Residual Algorithm for Non-Hermitian Linear Systems
Recommended article: Q3180743
Recommended article: A linear system solver based on a modified Krylov subspace method for breakdown recovery
Recommended article: Q4309409
Recommended article: Q4945815
Recommended article: On quasi-minimal residual approach of iterative algorithms for solving nonsymmetric linear systems
Recommended article: Iterative methods for solving \(Ax=b\), GMRES/FOM versus QMR/BiCG
Recommended article: On the QMR approach for iterative methods including coupled three-term recurrences for solving nonsymmetric linear systems
Recommended article: A quasi-minimal residual variant of the BiCORSTAB method for nonsymmetric linear systems
description: scientific article; zbMATH DE number 29619