Cholesky decomposition of a symmetric positive-definite matrix is similar to LU-decomposition of a general matrix.

On LU-decomposition, matrix A is represented as PA = LU. On Cholesky decomposition, matrix A is represented as A = LL ^T (or as A = U ^TU, which is the same).

We can see that on Cholesky decomposition, the pivot is not selected (but the factorization is stable) and there is no permutation matrix. Also, instead of matrices L and U, we only get one matrix multiplied by itself (therefore, this decomposition is also known as "square root of the matrix"). These properties occur because of the positive definiteness and symmetry of the matrix. One more advantage of Cholesky decomposition is the fact that it is twice as fast as LU-decomposition. Therefore, Cholesky decomposition is used when solving systems of linear equations with symmetric matrices.

There is no Cholesky decomposition for matrices which are not positive-definite, but another algorithm can be used. It decomposes an arbitrary symmetic matrix representing it as a product A = LDL ^T or A = UDU ^T. It should be noted that LDLT-decomposition is faster than LU-decomposition but slower than Cholesky decomposition, so it is better to use the latter, whenever possible.

Taking into account that matrix A is symmetric, it is usually given by its lower or upper triangular part. Therefore, after decomposition we get either matrix L or matrix U.

Subroutine SPDMatrixCholesky decomposes a symmetric matrix which is given by its lower or upper triangle and saves the result into the same triangular part of an input matrix.

This algorithm is transferred from the LAPACK library.

Report a bug

C#

C# 1.0 source.
cholesky.csharp.zip - Cholesky decomposition

C++

C++ source.
cholesky.cpp.zip - Cholesky decomposition
ablas.zip - optimized basic linear algebra subroutines with SSE2 support (for C++ sources only)

C++, multiple precision arithmetic

C++ source. MPFR/GMP is used.
GMP source is available from gmplib.org. MPFR source is available from www.mpfr.org.
cholesky.mpfr.zip - Cholesky decomposition
mpfr.zip - precompiled Win32 MPFR/GMP binaries

Delphi

Delphi source.
Can be compiled under FPC (in Delphi compatibility mode).
cholesky.delphi.zip - Cholesky decomposition

Visual Basic 6

Visual Basic 6 source.
cholesky.vb6.zip - Cholesky decomposition

Zonnon ^beta

Zonnon source.
Zonnon is an experimental language developed at ETH Zurich.
See www.zonnon.ethz.ch for more information.
cholesky.zonnon.zip - Cholesky decomposition