GitHub

QMR

QMR is a short-recurrence version of GMRES for solving $Ax = b$ approximately for $x$ where $A$ is a linear operator and $b$ the right-hand side vector. $A$ may be non-symmetric.

Usage

IterativeSolvers.qmr! — Function
qmr!(x, A, b; kwargs...) -> x, [history]

Solves the problem $Ax = b$ with the Quasi-Minimal Residual (QMR) method.

Arguments

  • x: Initial guess, will be updated in-place;
  • A: linear operator;
  • b: right-hand side.

Keywords

  • initially_zero::Bool: If true assumes that iszero(x) so that one matrix-vector product can be saved when computing the initial residual vector;
  • maxiter::Int = size(A, 2): maximum number of iterations;
  • abstol::Real = zero(real(eltype(b))), reltol::Real = sqrt(eps(real(eltype(b)))): absolute and relative tolerance for the stopping condition |r_k| ≤ max(reltol * |r_0|, abstol), where r_k = A * x_k - b
  • log::Bool: keep track of the residual norm in each iteration;
  • verbose::Bool: print convergence information during the iteration.

Return values

if log is false

  • x: approximate solution.

if log is true

  • x: approximate solution;

  • history: convergence history.

source

Implementation details

QMR exploits the tridiagonal structure of the Hessenberg matrix. Although QMR is similar to GMRES, where instead of using the Arnoldi process, a pair of biorthogonal vector spaces $V$ and $W$ is constructed via the Lanczos process. It requires that the adjoint of $A$ adjoint(A) be available.

QMR enables the computation of $V$ and $W$ via a three-term recurrence. A three-term recurrence for the projection onto the solution vector can also be constructed from these values, using the portion of the last column of the Hessenberg matrix. Therefore we pre-allocate only eight vectors.

For more detail on the implementation see the original paper [Freund1990] or [Saad2003].

Tip

QMR can be used as an iterator via qmr_iterable!. This makes it possible to access the next, current, and previous Krylov basis vectors during the iteration.

  • Saad2003Saad, Y. (2003). Interactive method for sparse linear system.
  • Freund1990Freund, W. R., & Nachtigal, N. M. (1990). QMR : for a Quasi-Minimal Residual Linear Method Systems. (December).
  • Saad2003Saad, Y. (2003). Interactive method for sparse linear system.
  • Freund1990Freund, W. R., & Nachtigal, N. M. (1990). QMR : for a Quasi-Minimal Residual Linear Method Systems. (December).