In numerical linear algebra, an incomplete LU factorization (abbreviated as ILU) of a matrix is a sparse approximation of the LU factorization often used as a preconditioner.
Introduction Consider a sparse linear system A x = b {\displaystyle Ax=b} . These are often solved by computing the factorization A = L U {\displaystyle A=LU} , with L lower unitriangular and U upper triangular. One then solves L y = b {\displaystyle Ly=b} , U x = y {\displaystyle Ux=y} , 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 — a phenomenon called fill-in. 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 Minimum degree algorithm. An incomplete factorization instead seeks triangular matrices L, U such that A ≈ L U {\displaystyle A\approx LU} rather than A = L U {\displaystyle A=LU} . Solving for L U x = b {\displaystyle LUx=b} can be done quickly but does not yield the exact solution to A x = b {\displaystyle Ax=b} . So, we instead use the matrix M = L U {\displaystyle M=LU} as a preconditioner in another iterative solution algorithm such as the conjugate gradient method or GMRES.
Definition For a given matrix A ∈ R n × n {\displaystyle A\in \mathbb {R} ^{n\times n}} one defines the graph G ( A ) {\displaystyle G(A)} as
G ( A ) := { ( i , j ) ∈ N 2 : A i j ≠ 0 } , {\displaystyle G(A):=\left\lbrace (i,j)\in \mathbb {N} ^{2}:A_{ij}\neq 0\right\rbrace \,,}
which is used to define the conditions a sparsity pattern S {\displaystyle S} needs to fulfill
S ⊂ { 1 , … , n } 2 , { ( i , i ) : 1 ≤ i ≤ n } ⊂ S , G ( A ) ⊂ S . {\displaystyle S\subset \left\lbrace 1,\dots ,n\right\rbrace ^{2}\,,\quad \left\lbrace (i,i):1\leq i\leq n\right\rbrace \subset S\,,\quad G(A)\subset S\,.}
A decomposition of the form A = L U − R {\displaystyle A=LU-R} where the following hold
L ∈ R n × n {\displaystyle L\in \mathbb {R} ^{n\times n}} is a lower unitriangular matrix
U ∈ R n × n {\displaystyle U\in \mathbb {R} ^{n\times n}} is an upper triangular matrix
L , U {\displaystyle L,U} are zero outside of the sparsity pattern: L i j = U i j = 0 ∀ ( i , j ) ∉ S {\displaystyle L_{ij}=U_{ij}=0\quad \forall \;(i,j)\notin S}
R ∈ R n × n {\displaystyle R\in \mathbb {R} ^{n\times n}} is zero within the sparsity pattern: R i j = 0 ∀ ( i , j ) ∈ S {\displaystyle R_{ij}=0\quad \forall \;(i,j)\in S}
is called an incomplete LU decomposition (with respect to the sparsity pattern S {\displaystyle S} ). 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).
… excerpt ends here. Continue reading the full article.
