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.
For from to :
- For from to :
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
- Incomplete Cholesky factorization at CFD Online wiki
- Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd ed.), Johns Hopkins, ISBN 978-0-8018-5414-9. See Section 10.3.2.
|This applied mathematics-related article is a stub. You can help Wikipedia by expanding it.|