Incomplete Cholesky factorization

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In numerical analysis, an incomplete Cholesky factorization of a symmetric positive definite matrix is a sparse approximation of the Cholesky factorization. Incomplete Cholesky factorization are often used as a preconditioner for algorithms like the conjugate gradient method.

The Cholesky factorization of a positive definite matrix A is A = LL* where L is a lower triangular matrix. An incomplete Cholesky factorization is given by a sparse lower triangular matrix K that is in some sense close to L. The corresponding preconditioner is KK*.

One popular way to find such a matrix K is to use the algorithm for finding the exact Cholesky decomposition, except that any entry is set to zero if the corresponding entry in A is also zero. This gives an incomplete Cholesky factorization which is as sparse as the matrix A.

Algorithm[edit]

For i from 1 to N:


L_{ii}  = \left( {a_{ii}  - \sum\limits_{k = 1}^{i - 1} {L_{ik}^2 } } \right)^{{1 \over 2}}
For j from i+1 to N:

L_{ji}  = {1 \over {L_{ii} }}\left( {a_{ij}  - \sum\limits_{k = 1}^{i - 1} {L_{ik} L_{jk} } } \right)

References[edit]