Incomplete Cholesky factorization
Encyclopedia
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.
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
, an incomplete Cholesky factorization of a symmetric positive definite matrix is a sparse
Sparse matrix
In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . The term itself was coined by Harry M. Markowitz....
approximation of the Cholesky factorization. Incomplete Cholesky factorization are often used as a preconditioner
Preconditioner
In mathematics, preconditioning is a procedure of an application of a transformation, called the preconditioner, that conditions a given problem into a form that is more suitable for numerical solution. Preconditioning is typically related to reducing a condition number of the problem...
for algorithms like the conjugate gradient method
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 symmetric and positive-definite. The conjugate gradient method is an iterative method, so it can be applied to sparse systems that are too...
.
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.