octave: Iterative Techniques
22.3 Iterative Techniques Applied to Sparse Matrices
====================================================
The left division ‘\’ and right division ‘/’ operators, discussed in the
previous section, use direct solvers to resolve a linear equation of the
form ‘X = A \ B’ or ‘X = B / A’. Octave also includes a number of
functions to solve sparse linear equations using iterative techniques.
-- : X = pcg (A, B, TOL, MAXIT, M1, M2, X0, ...)
-- : [X, FLAG, RELRES, ITER, RESVEC, EIGEST] = pcg (...)
Solve the linear system of equations ‘A * X = B’ by means of the
Preconditioned Conjugate Gradient iterative method.
The input arguments are
• A can be either a square (preferably sparse) matrix or a
function handle, inline function or string containing the name
of a function which computes ‘A * X’. In principle, A should
be symmetric and positive definite; if ‘pcg’ finds A not to be
positive definite, a warning is printed and the FLAG output
will be set.
• B is the right-hand side vector.
• TOL is the required relative tolerance for the residual error,
‘B - A * X’. The iteration stops if
‘norm (B - A * X)’ ≤ TOL * norm (B). If TOL is omitted or
empty then a tolerance of 1e-6 is used.
• MAXIT is the maximum allowable number of iterations; if MAXIT
is omitted or empty then a value of 20 is used.
• M = M1 * M2 is the (left) preconditioning matrix, so that the
iteration is (theoretically) equivalent to solving by ‘pcg’
‘P * X = M \ B’, with ‘P = M \ A’. Note that a proper choice
of the preconditioner may dramatically improve the overall
performance of the method. Instead of matrices M1 and M2, the
user may pass two functions which return the results of
applying the inverse of M1 and M2 to a vector (usually this is
the preferred way of using the preconditioner). If M1 is
omitted or empty ‘[]’ then no preconditioning is applied. If
M2 is omitted, M = M1 will be used as a preconditioner.
• X0 is the initial guess. If X0 is omitted or empty then the
function sets X0 to a zero vector by default.
The arguments which follow X0 are treated as parameters, and passed
in a proper way to any of the functions (A or M) which are passed
to ‘pcg’. See the examples below for further details. The output
arguments are
• X is the computed approximation to the solution of
‘A * X = B’.
• FLAG reports on the convergence. A value of 0 means the
solution converged and the tolerance criterion given by TOL is
satisfied. A value of 1 means that the MAXIT limit for the
iteration count was reached. A value of 3 indicates that the
(preconditioned) matrix was found not to be positive definite.
• RELRES is the ratio of the final residual to its initial
value, measured in the Euclidean norm.
• ITER is the actual number of iterations performed.
• RESVEC describes the convergence history of the method.
‘RESVEC(i,1)’ is the Euclidean norm of the residual, and
‘RESVEC(i,2)’ is the preconditioned residual norm, after the
(I-1)-th iteration, ‘I = 1, 2, ..., ITER+1’. The
preconditioned residual norm is defined as ‘norm (R) ^ 2 = R'
* (M \ R)’ where ‘R = B - A * X’, see also the description of
M. If EIGEST is not required, only ‘RESVEC(:,1)’ is returned.
• EIGEST returns the estimate for the smallest ‘EIGEST(1)’ and
largest ‘EIGEST(2)’ eigenvalues of the preconditioned matrix
‘P = M \ A’. In particular, if no preconditioning is used,
the estimates for the extreme eigenvalues of A are returned.
‘EIGEST(1)’ is an overestimate and ‘EIGEST(2)’ is an
underestimate, so that ‘EIGEST(2) / EIGEST(1)’ is a lower
bound for ‘cond (P, 2)’, which nevertheless in the limit
should theoretically be equal to the actual value of the
condition number. The method which computes EIGEST works only
for symmetric positive definite A and M, and the user is
responsible for verifying this assumption.
Let us consider a trivial problem with a diagonal matrix (we
exploit the sparsity of A)
n = 10;
A = diag (sparse (1:n));
b = rand (n, 1);
[l, u, p] = ilu (A, struct ("droptol", 1.e-3));
EXAMPLE 1: Simplest use of ‘pcg’
x = pcg (A, b)
EXAMPLE 2: ‘pcg’ with a function which computes ‘A * X’
function y = apply_a (x)
y = [1:N]' .* x;
endfunction
x = pcg ("apply_a", b)
EXAMPLE 3: ‘pcg’ with a preconditioner: L * U
x = pcg (A, b, 1.e-6, 500, l*u)
EXAMPLE 4: ‘pcg’ with a preconditioner: L * U. Faster than EXAMPLE
3 since lower and upper triangular matrices are easier to invert
x = pcg (A, b, 1.e-6, 500, l, u)
EXAMPLE 5: Preconditioned iteration, with full diagnostics. The
preconditioner (quite strange, because even the original matrix A
is trivial) is defined as a function
function y = apply_m (x)
k = floor (length (x) - 2);
y = x;
y(1:k) = x(1:k) ./ [1:k]';
endfunction
[x, flag, relres, iter, resvec, eigest] = ...
pcg (A, b, [], [], "apply_m");
semilogy (1:iter+1, resvec);
EXAMPLE 6: Finally, a preconditioner which depends on a parameter
K.
function y = apply_M (x, varargin)
K = varargin{1};
y = x;
y(1:K) = x(1:K) ./ [1:K]';
endfunction
[x, flag, relres, iter, resvec, eigest] = ...
pcg (A, b, [], [], "apply_m", [], [], 3)
References:
1. C.T. Kelley, ‘Iterative Methods for Linear and Nonlinear
Equations’, SIAM, 1995. (the base PCG algorithm)
2. Y. Saad, ‘Iterative Methods for Sparse Linear Systems’, PWS
1996. (condition number estimate from PCG) Revised version of
this book is available online at
<http://www-users.cs.umn.edu/~saad/books.html>
See also: 
sparse XREFsparse, pcr XREFpcr.
-- : X = pcr (A, B, TOL, MAXIT, M, X0, ...)
-- : [X, FLAG, RELRES, ITER, RESVEC] = pcr (...)
Solve the linear system of equations ‘A * X = B’ by means of the
Preconditioned Conjugate Residuals iterative method.
The input arguments are
• A can be either a square (preferably sparse) matrix or a
function handle, inline function or string containing the name
of a function which computes ‘A * X’. In principle A should
be symmetric and non-singular; if ‘pcr’ finds A to be
numerically singular, you will get a warning message and the
FLAG output parameter will be set.
• B is the right hand side vector.
• TOL is the required relative tolerance for the residual error,
‘B - A * X’. The iteration stops if ‘norm (B - A * X) <= TOL
* norm (B - A * X0)’. If TOL is empty or is omitted, the
function sets ‘TOL = 1e-6’ by default.
• MAXIT is the maximum allowable number of iterations; if ‘[]’
is supplied for ‘maxit’, or ‘pcr’ has less arguments, a
default value equal to 20 is used.
• M is the (left) preconditioning matrix, so that the iteration
is (theoretically) equivalent to solving by ‘pcr’ ‘P * X = M \
B’, with ‘P = M \ A’. Note that a proper choice of the
preconditioner may dramatically improve the overall
performance of the method. Instead of matrix M, the user may
pass a function which returns the results of applying the
inverse of M to a vector (usually this is the preferred way of
using the preconditioner). If ‘[]’ is supplied for M, or M is
omitted, no preconditioning is applied.
• X0 is the initial guess. If X0 is empty or omitted, the
function sets X0 to a zero vector by default.
The arguments which follow X0 are treated as parameters, and passed
in a proper way to any of the functions (A or M) which are passed
to ‘pcr’. See the examples below for further details.
The output arguments are
• X is the computed approximation to the solution of ‘A * X =
B’.
• FLAG reports on the convergence. ‘FLAG = 0’ means the
solution converged and the tolerance criterion given by TOL is
satisfied. ‘FLAG = 1’ means that the MAXIT limit for the
iteration count was reached. ‘FLAG = 3’ reports a ‘pcr’
breakdown, see [1] for details.
• RELRES is the ratio of the final residual to its initial
value, measured in the Euclidean norm.
• ITER is the actual number of iterations performed.
• RESVEC describes the convergence history of the method, so
that ‘RESVEC (i)’ contains the Euclidean norms of the residual
after the (I-1)-th iteration, ‘I = 1,2, ..., ITER+1’.
Let us consider a trivial problem with a diagonal matrix (we
exploit the sparsity of A)
n = 10;
A = sparse (diag (1:n));
b = rand (N, 1);
EXAMPLE 1: Simplest use of ‘pcr’
x = pcr (A, b)
EXAMPLE 2: ‘pcr’ with a function which computes ‘A * X’.
function y = apply_a (x)
y = [1:10]' .* x;
endfunction
x = pcr ("apply_a", b)
EXAMPLE 3: Preconditioned iteration, with full diagnostics. The
preconditioner (quite strange, because even the original matrix A
is trivial) is defined as a function
function y = apply_m (x)
k = floor (length (x) - 2);
y = x;
y(1:k) = x(1:k) ./ [1:k]';
endfunction
[x, flag, relres, iter, resvec] = ...
pcr (A, b, [], [], "apply_m")
semilogy ([1:iter+1], resvec);
EXAMPLE 4: Finally, a preconditioner which depends on a parameter
K.
function y = apply_m (x, varargin)
k = varargin{1};
y = x;
y(1:k) = x(1:k) ./ [1:k]';
endfunction
[x, flag, relres, iter, resvec] = ...
pcr (A, b, [], [], "apply_m"', [], 3)
References:
[1] W. Hackbusch, ‘Iterative Solution of Large Sparse Systems of
Equations’, section 9.5.4; Springer, 1994
See also: sparse XREFsparse, pcg XREFpcg.
The speed with which an iterative solver converges to a solution can
be accelerated with the use of a pre-conditioning matrix M. In this
case the linear equation ‘M^-1 * X = M^-1 * A \ B’ is solved instead.
Typical pre-conditioning matrices are partial factorizations of the
original matrix.
-- : L = ichol (A)
-- : L = ichol (A, OPTS)
Compute the incomplete Cholesky factorization of the sparse square
matrix A.
By default, ‘ichol’ uses only the lower triangle of A and produces
a lower triangular factor L such that L*L’ approximates A.
The factor given by this routine may be useful as a preconditioner
for a system of linear equations being solved by iterative methods
such as PCG (Preconditioned Conjugate Gradient).
The factorization may be modified by passing options in a structure
OPTS. The option name is a field of the structure and the setting
is the value of field. Names and specifiers are case sensitive.
type
Type of factorization.
"nofill" (default)
Incomplete Cholesky factorization with no fill-in
(IC(0)).
"ict"
Incomplete Cholesky factorization with threshold dropping
(ICT).
diagcomp
A non-negative scalar ALPHA for incomplete Cholesky
factorization of ‘A + ALPHA * diag (diag (A))’ instead of A.
This can be useful when A is not positive definite. The
default value is 0.
droptol
A non-negative scalar specifying the drop tolerance for
factorization if performing ICT. The default value is 0 which
produces the complete Cholesky factorization.
Non-diagonal entries of L are set to 0 unless
‘abs (L(i,j)) >= droptol * norm (A(j:end, j), 1)’.
michol
Modified incomplete Cholesky factorization:
"off" (default)
Row and column sums are not necessarily preserved.
"on"
The diagonal of L is modified so that row (and column)
sums are preserved even when elements have been dropped
during the factorization. The relationship preserved is:
‘A * e = L * L' * e’, where e is a vector of ones.
shape
"lower" (default)
Use only the lower triangle of A and return a lower
triangular factor L such that L*L’ approximates A.
"upper"
Use only the upper triangle of A and return an upper
triangular factor U such that ‘U'*U’ approximates A.
EXAMPLES
The following problem demonstrates how to factorize a sample
symmetric positive definite matrix with the full Cholesky
decomposition and with the incomplete one.
A = [ 0.37, -0.05, -0.05, -0.07;
-0.05, 0.116, 0.0, -0.05;
-0.05, 0.0, 0.116, -0.05;
-0.07, -0.05, -0.05, 0.202];
A = sparse (A);
nnz (tril (A))
ans = 9
L = chol (A, "lower");
nnz (L)
ans = 10
norm (A - L * L', "fro") / norm (A, "fro")
ans = 1.1993e-16
opts.type = "nofill";
L = ichol (A, opts);
nnz (L)
ans = 9
norm (A - L * L', "fro") / norm (A, "fro")
ans = 0.019736
Another example for decomposition is a finite difference matrix
used to solve a boundary value problem on the unit square.
nx = 400; ny = 200;
hx = 1 / (nx + 1); hy = 1 / (ny + 1);
Dxx = spdiags ([ones(nx, 1), -2*ones(nx, 1), ones(nx, 1)],
[-1 0 1 ], nx, nx) / (hx ^ 2);
Dyy = spdiags ([ones(ny, 1), -2*ones(ny, 1), ones(ny, 1)],
[-1 0 1 ], ny, ny) / (hy ^ 2);
A = -kron (Dxx, speye (ny)) - kron (speye (nx), Dyy);
nnz (tril (A))
ans = 239400
opts.type = "nofill";
L = ichol (A, opts);
nnz (tril (A))
ans = 239400
norm (A - L * L', "fro") / norm (A, "fro")
ans = 0.062327
References for implemented algorithms:
[1] Y. Saad. "Preconditioning Techniques." ‘Iterative Methods for
Sparse Linear Systems’, PWS Publishing Company, 1996.
[2] M. Jones, P. Plassmann: ‘An Improved Incomplete Cholesky
Factorization’, 1992.
DONTPRINTYET See also: chol XREFchol, ilu XREFilu, *notepcg:
DONTPRINTYET See also: chol XREFchol, ilu XREFilu, pcg
XREFpcg.
-- : ilu (A)
-- : ilu (A, OPTS)
-- : [L, U] = ilu (...)
-- : [L, U, P] = ilu (...)
Compute the incomplete LU factorization of the sparse square matrix
A.
‘ilu’ returns a unit lower triangular matrix L, an upper triangular
matrix U, and optionally a permutation matrix P, such that ‘L*U’
approximates ‘P*A’.
The factors given by this routine may be useful as preconditioners
for a system of linear equations being solved by iterative methods
such as BICG (BiConjugate Gradients) or GMRES (Generalized Minimum
Residual Method).
The factorization may be modified by passing options in a structure
OPTS. The option name is a field of the structure and the setting
is the value of field. Names and specifiers are case sensitive.
‘type’
Type of factorization.
"nofill"
ILU factorization with no fill-in (ILU(0)).
Additional supported options: ‘milu’.
"crout"
Crout version of ILU factorization (ILUC).
Additional supported options: ‘milu’, ‘droptol’.
"ilutp" (default)
ILU factorization with threshold and pivoting.
Additional supported options: ‘milu’, ‘droptol’, ‘udiag’,
‘thresh’.
‘droptol’
A non-negative scalar specifying the drop tolerance for
factorization. The default value is 0 which produces the
complete LU factorization.
Non-diagonal entries of U are set to 0 unless
‘abs (U(i,j)) >= droptol * norm (A(:,j))’.
Non-diagonal entries of L are set to 0 unless
‘abs (L(i,j)) >= droptol * norm (A(:,j))/U(j,j)’.
‘milu’
Modified incomplete LU factorization:
"row"
Row-sum modified incomplete LU factorization. The
factorization preserves row sums: ‘A * e = L * U * e’,
where e is a vector of ones.
"col"
Column-sum modified incomplete LU factorization. The
factorization preserves column sums: ‘e' * A = e' * L *
U’.
"off" (default)
Row and column sums are not necessarily preserved.
‘udiag’
If true, any zeros on the diagonal of the upper triangular
factor are replaced by the local drop tolerance ‘droptol *
norm (A(:,j))/U(j,j)’. The default is false.
‘thresh’
Pivot threshold for factorization. It can range between 0
(diagonal pivoting) and 1 (default), where the maximum
magnitude entry in the column is chosen to be the pivot.
If ‘ilu’ is called with just one output, the returned matrix is ‘L
+ U - speye (size (A))’, where L is unit lower triangular and U is
upper triangular.
With two outputs, ‘ilu’ returns a unit lower triangular matrix L
and an upper triangular matrix U. For OPTS.type == "ilutp", one of
the factors is permuted based on the value of OPTS.milu. When
OPTS.milu == "row", U is a column permuted upper triangular factor.
Otherwise, L is a row-permuted unit lower triangular factor.
If there are three named outputs and OPTS.milu != "row", P is
returned such that L and U are incomplete factors of ‘P*A’. When
OPTS.milu == "row", P is returned such that L and U are incomplete
factors of ‘A*P’.
EXAMPLES
A = gallery ("neumann", 1600) + speye (1600);
opts.type = "nofill";
nnz (A)
ans = 7840
nnz (lu (A))
ans = 126478
nnz (ilu (A, opts))
ans = 7840
This shows that A has 7,840 nonzeros, the complete LU factorization
has 126,478 nonzeros, and the incomplete LU factorization, with 0
level of fill-in, has 7,840 nonzeros, the same amount as A. Taken
from: http://www.mathworks.com/help/matlab/ref/ilu.html
A = gallery ("wathen", 10, 10);
b = sum (A, 2);
tol = 1e-8;
maxit = 50;
opts.type = "crout";
opts.droptol = 1e-4;
[L, U] = ilu (A, opts);
x = bicg (A, b, tol, maxit, L, U);
norm (A * x - b, inf)
This example uses ILU as preconditioner for a random FEM-Matrix,
which has a large condition number. Without L and U BICG would not
converge.
DONTPRINTYET See also: lu XREFlu, ichol XREFichol, *notebicg:
DONTPRINTYET See also: lu XREFlu, ichol XREFichol, bicg
XREFbicg, gmres XREFgmres.
Info Catalog
octave: Sparse Linear Algebra
octave: Sparse Matrices
octave: Real Life Example