Incomplete Cholesky factorization


In numerical analysis, an incomplete Cholesky factorization of a symmetric positive definite matrix is a sparse approximation of the Cholesky factorization. An incomplete Cholesky factorization is 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

For from to :

Implementation

Implementation of the incomplete Cholesky factorization in the Octave scripting language. The factorization is stored as a lower triangular matrix, with the elements in the upper triangle set to zero.

function a = ichol
n = size;
for k=1:n
a = sqrt;
for i=:n
if
a = a/a;
endif
endfor
for j=:n
for i=j:n
if
a = a-a*a;
endif
endfor
endfor
endfor
for i=1:n
for j=i+1:n
a = 0;
endfor
endfor
endfunction