# 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 $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)$

## Implementation

Implementation of the incomplete Cholesky factorizaton 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(a)
n = size(a,1);

for k=1:n
a(k,k) = sqrt(a(k,k));
for i=(k+1):n
if (a(i,k)!=0)
a(i,k) = a(i,k)/a(k,k);
endif
endfor
for j=(k+1):n
for i=j:n
if (a(i,j)!=0)
a(i,j) = a(i,j)-a(i,k)*a(j,k);
endif
endfor
endfor
endfor

for i=1:n
for j=i+1:n
a(i,j) = 0;
endfor
endfor
endfunction