Incomplete LU factorization
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 formula_1. These are often solved by computing the factorization formula_2, with "L" lower unitriangular and "U" upper triangular. One then solves formula_3, formula_4, 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 formula_5 rather than formula_2. Solving for formula_7 can be done quickly but does not yield the exact solution to formula_1. So, we instead use the matrix formula_9 as a preconditioner in another iterative solution algorithm such as the conjugate gradient method or GMRES. Definition. For a given matrix formula_10 one defines the graph formula_11 as which is used to define  the conditions a "sparsity patterns" formula_13 needs to fulfill A decomposition of the form formula_15 where the following hold is called an incomplete LU decomposition (with respect to the sparsity pattern formula_13). 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). Stability. Concerning the stability of the ILU the following theorem was proven by Meijerink  and van der Vorst. Let formula_23 be an M-matrix, the (complete) LU decomposition given by formula_24, and the ILU by formula_25. Then holds. Thus, the ILU is at least as stable as the (complete) LU decomposition. 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". More accurate ILU preconditioners require more memory, to such an extent that eventually the running time of the algorithm increases even though the total number of iterations decreases. Consequently, there is a cost/accuracy trade-off that users must evaluate, typically on a case-by-case basis depending on the family of linear systems to be solved. The ILU factorization can be performed as a fixed-point iteration in a highly parallel way.