In
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods th ...
, an incomplete Cholesky factorization of a symmetric
positive definite matrix
In mathematics, a symmetric matrix M with real entries is positive-definite if the real number z^\textsfMz is positive for every nonzero real column vector z, where z^\textsf is the transpose of More generally, a Hermitian matrix (that is, a ...
is a
sparse
Sparse is a computer software tool designed to find possible coding faults in the Linux kernel. Unlike other such tools, this static analysis tool was initially designed to only flag constructs that were likely to be of interest to kernel de ...
approximation of the
Cholesky factorization. An incomplete Cholesky factorization is often used as a
preconditioner
In mathematics, preconditioning is the application of a transformation, called the preconditioner, that conditions a given problem into a form that is more suitable for numerical solving methods. Preconditioning is typically related to reducing ...
for algorithms like the
conjugate gradient method
In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-definite. The conjugate gradient method is often implemented as an iter ...
.
The Cholesky factorization of a positive definite matrix ''A'' is ''A'' = ''LL''* where ''L'' is a
lower triangular matrix
In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...
. 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 in which ''K'' has the same sparsity pattern as ''A'' (any entry of ''K'' 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
:
:
: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(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
References
Incomplete Cholesky factorizationat CFD Online wiki
* . See Section 10.3.2.
{{Numerical linear algebra
Numerical linear algebra