MATLAB Function Reference

ilu - Sparse incomplete LU factorization

Syntax

ilu(A,setup) [L,U] = ilu(A,setup) [L,U,P] = ilu(A,setup)

Description

ilu produces a unit lower triangular matrix, an upper triangular matrix, and a permutation matrix.

ilu(A,setup) computes the incomplete LU factorization of A. setup is an input structure with up to five setup options. The fields must be named exactly as shown in the table below. You can include any number of these fields in the structure and define them in any order. Any additional fields are ignored.

Field Name	Description
`type`	Type of factorization. Values for `type` include: `'nofill'`—Performs ILU factorization with `0` level of fill in, known as ILU(0). With `type` set to `'nofill'`, only the `milu` setup option is used; all other fields are ignored. `'crout'`—Performs the Crout version of ILU factorization, known as ILUC. With `type` set to `'crout'`, only the `droptol` and `milu` setup options are used; all other fields are ignored. `'ilutp'` (default)—Performs ILU factorization with threshold and pivoting. If `type` is not specified, the ILU factorization with pivoting ILUTP is performed. Pivoting is never performed with `type` set to `'nofill'` or `'crout'`.
`droptol`	Drop tolerance of the incomplete LU factorization. `droptol` is a non-negative scalar. The default value is `0`, which produces the complete LU factorization. The nonzero entries of `U` satisfy abs(U(i,j)) >= droptolnorm((A:,j)), with the exception of the diagonal entries, which are retained regardless of satisfying the criterion. The entries of `L` are tested against the local drop tolerance before being scaled by the pivot, so for nonzeros in `L` abs(L(i,j)) >= droptolnorm(A(:,j))/U(j,j).
`milu`	Modified incomplete LU factorization. Values for `milu` include: `'row'`—Produces the row-sum modified incomplete LU factorization. Entries from the newly-formed column of the factors are subtracted from the diagonal of the upper triangular factor, `U`, preserving column sums. That is, `Ae = LUe`, where `e` is the vector of ones. `'col'`—Produces the column-sum modified incomplete LU factorization. Entries from the newly-formed column of the factors are subtracted from the diagonal of the upper triangular factor, `U`, preserving column sums. That is, `e'A = e'LU`. `'off'` (default)—No modified incomplete LU factorization is produced.
`udiag`	If `udiag` is `1`, any zeros on the diagonal of the upper triangular factor are replaced by the local drop tolerance. The default is `0`.
`thresh`	Pivot threshold between `0` (forces diagonal pivoting) and `1`, the default, which always chooses the maximum magnitude entry in the column to be the pivot.

ilu(A,setup) returns L+U-speye(size(A)), where L is a unit lower triangular matrix and U is an upper triangular matrix.

[L,U] = ilu(A,setup) returns a unit lower triangular matrix in L and an upper triangular matrix in U.

[L,U,P] = ilu(A,setup) returns a unit lower triangular matrix in L, an upper triangular matrix in U, and a permutation matrix in P.

Remarks

These incomplete factorizations may be useful as preconditioners for a system of linear equations being solved by iterative methods such as BICG (BiConjugate Gradients), GMRES (Generalized Minimum Residual Method).

Limitations

ilu works on sparse square matrices only.

Examples

Start with a sparse matrix and compute the LU factorization.

A = gallery('neumann', 1600) + speye(1600);
setup.type = 'crout';
setup.milu = 'row';
setup.droptol = 0.1;
[L,U] = ilu(A,setup);
e = ones(size(A,2),1);
norm(A*e-L*U*e)

ans =

  1.4251e-014

This shows that A and L*U, where L and U are given by the modified Crout ILU, have the same row-sum.

Start with a sparse matrix and compute the LU factorization.

A = gallery('neumann', 1600) + speye(1600);
setup.type = 'nofill';
nnz(A)
ans =

        7840

nnz(lu(A))
ans =

      126478

nnz(ilu(A,setup))
ans =

        7840

This shows that A has 7840 nonzeros, the complete LU factorization has 126478 nonzeros, and the incomplete LU factorization, with 0 level of fill-in, has 7840 nonzeros, the same amount as A.

References

[1] Saad, Yousef, Iterative Methods for Sparse Linear Systems, PWS Publishing Company, 1996, Chapter 10 - Preconditioning Techniques.

ifftshift

im2frame