Incomplete LU factorization: Difference between revisions

Revision as of 10:06, 14 March 2018

Revision as of 10:14, 14 March 2018

Line 1:

In [[numerical linear algebra]], an '''incomplete LU factorization''' of a [[matrix (mathematics)|matrix]] is a [[sparse matrix|sparse]] approximation of the [[LU factorization]] often used as a [[preconditioner]].

== Introduction ==

Consider a sparse linear system <math>Ax = b</math>. These are often solved by computing the factorization <math>A = LU</math>, with ''L'' [[Triangular_matrix#Unitriangular_matrix|lower unitriangular]] and ''U'' [[Triangular_matrix|upper triangular]].

One then solves <math>Ly = b</math>, <math>Ux = y</math>, which can be done efficiently because the matrices are triangular.

Line 9 ⟶ 10:

An incomplete factorization instead seeks triangular matrices ''L'', ''U'' such that <math>A \approx LU</math> rather than <math>A = LU</math>. Solving for <math>LUx = b</math> can be done quickly but does not yield the exact solution to <math>Ax = b</math>. So, we instead use the matrix <math>M = LU</math> as a preconditioner in another iterative solution algorithm such as the [[conjugate gradient method]] or [[GMRES]].

== Definition ==

The sparsity pattern of ''L'' and ''U'' is often chosen to be the same as the sparsity pattern of the original matrix ''A''. If the underlying matrix structure can be referenced by pointers instead of copied, the only extra memory required is for the entries of ''L'' and ''U''. This preconditioner is called ILU(0).

== Generalizations ==

One can obtain a more accurate preconditioner by allowing some level of extra fill in the factorization. A common choice is to use the sparsity pattern of ''A²'' instead of ''A''; this matrix is appreciably more dense than ''A'', but still sparse over all. This preconditioner is called ILU(1). One can then generalize this procedure; the ILU(k) preconditioner of a matrix ''A'' is the incomplete LU factorization with the sparsity pattern of the matrix ''A^k+1''.