`gmres`

Solves a square linear system with the generalized minimal residual method.

Syntax

x = gmres(A, b)

Solves A*x = b with default settings.

x = gmres(A, b, restart, tol, maxit)

Restarts every restart inner steps; [] runs without restarts.

x = gmres(A, b, restart, tol, maxit, M1, M2, x0)

Adds a preconditioner M = M1*M2 and an initial guess x0.

[x, flag, relres, iter, resvec] = gmres(___)

Also returns the flag, final relative residual, iteration counts [outer inner] and residual history.

Description

At step k, GMRES picks the vector in the Krylov subspace spanned by b, A*b, ..., A^(k-1)*b that minimizes the residual. It handles any square matrix, symmetric or not, and its residual never increases. The price is memory: it stores all k basis vectors, and the work per step grows with k.

Restarting after restart steps caps that cost, but may slow convergence or even stall it. Use [] for small problems and a restart value for large ones.

Input arguments

A: Square coefficient matrix, or a function handle that returns A*x.
b: Right-hand side column vector.
restart: Inner iterations before restarting. [] or a value of size(A,1) means no restart.
tol: Relative residual tolerance; default 1e-6.
maxit: Maximum number of outer iterations.
M1, M2: Preconditioner factors.
x0: Initial guess; default zeros.

Output arguments

x: The computed solution.
flag: 0 if converged, 1 if maxit was reached, 2 for an ill-conditioned preconditioner, 3 if stagnated.
relres: Final relative residual.
iter: Two-element vector [outer inner] locating the iteration at which x was found.
resvec: Residual norms at each inner iteration.

Example

Without and with a restart

A = sparse(diag(4*ones(5,1)) + diag(ones(4,1),1) + diag(ones(4,1),-1));
b = (1:5)';
[x, flag, relres, iter] = gmres(A, b, [], 1e-10, 5);
fprintf('flag = %d, iter = [%d %d]\n', flag, iter)
disp(x')
[x, flag, relres, iter] = gmres(A, b, 2, 1e-10, 20);
fprintf('flag = %d, relres < 1e-10: %d\n', flag, relres < 1e-10)

Output

flag = 0, iter = [1 5]
    0.1679    0.3282    0.5192    0.5949    1.1013
flag = 0, relres < 1e-10: 1

gmres