Cholesky

Cholesky decomposition, also called Cholesky factorization, is a factorization of a real symmetric positive-definite matrix A into the product A = L L^T, where L is a lower triangular matrix with positive diagonal entries. In the complex case, for Hermitian positive-definite matrices, the factorization can be written as A = L L^H, where L is lower triangular and L^H denotes the conjugate transpose. There is also an upper-triangular variant, A = U^T U or A = U^H U, using an upper triangular factor U.

Existence and uniqueness: A admits a Cholesky factorization if and only if A is positive definite. When it exists, the factor L is unique with positive diagonal elements (assuming the real case).

Algorithm and complexity: The standard algorithm computes L column by column. For k = 1 to n, set L[k,k] = sqrt(A[k,k] - sum_{s<k} L[k,s]^2); for i = k+1 to n, set L[i,k] = (A[i,k] - sum_{s<k} L[i,s] L[k,s]) / L[k,k]. The result satisfies A = L L^T (or A = L L^H in the complex case). The operation count is O(n^3/3) and, for SPD matrices, no pivoting is required, providing numerical stability. The decomposition may be computed in place.

Applications: Cholesky is widely used to solve linear systems with symmetric positive-definite matrices by forward and backward substitution, to compute determinants and inverses, and to simulate samples from multivariate normal distributions. It is also used in Kalman filtering and various numerical linear algebra routines.

History: The method is named after André-Louis Cholesky, a French engineer who introduced it in the early 20th century.