Incomplete LU factorization: Difference between revisions

Revision as of 14:05, 10 May 2016

Revision as of 07:41, 28 March 2017

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-lower triangular and ''U'' upper triangular. One then solves <math>Ly = b</math>, <math>Ux = y</math>, which can be done quicklyefficient 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]].