Incomplete LU factorization: Difference between revisions

Revision as of 07:44, 28 March 2017

Revision as of 10:01, 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]].

Consider a sparse linear system <math>Ax = b</math>. These are often solved by computing the factorization <math>A = LU</math>, with ''L'' unit-[[Triangular_matrix#Unitriangular_matrix|lower triangularunitriangular]] 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.

For a typical sparse matrix, the LU factors can be much less sparse than the original matrix. The memory requirements for using a direct solver can then become a bottleneck in solving linear systems. One can combat this problem by using fill-reducing reorderings of the matrix's unknowns, such as the [[Cuthill-McKee algorithm|Cuthill-McKee ordering]].