Cholesky Decomposition
The efficient square-root factorization reserved for symmetric positive-definite matrices.
The factorization
For a symmetric positive-definite matrix A, the Cholesky decomposition writes A = L L^T, where L is lower triangular with positive diagonal entries. It is a specialized, more efficient form of LU that exploits symmetry, using about half the arithmetic and half the storage because only one triangular factor is needed.
Requirements and by-product
Cholesky exists and is unique exactly when A is symmetric positive definite. This gives a practical test: attempting the factorization and checking that every diagonal square root is of a positive number confirms positive definiteness. If the algorithm encounters a nonpositive pivot, the matrix is not positive definite, and it fails cleanly.
Solving systems
As with LU, solving Ax = b after Cholesky is two triangular solves: forward substitution with L, then back substitution with L^T. Because no pivoting is required for positive-definite matrices, the process is both fast and numerically stable, making Cholesky the method of choice for the symmetric systems that arise from least squares and physics discretizations.
Where it appears
- normal equations A^T A x = A^T b in least squares
- covariance matrices in statistics and Kalman filtering
- sampling correlated Gaussian random vectors
- stiffness matrices in finite-element structural analysis
import numpy as np
A = np.array([[4.0, 2.0], [2.0, 3.0]]) # SPD
L = np.linalg.cholesky(A)
print(np.allclose(L @ L.T, A)) # True
# solve A x = b
b = np.array([2.0, 1.0])
y = np.linalg.solve(L, b)
x = np.linalg.solve(L.T, y)Symmetric positive-definite operators from finite-element models of magnets and structures are routinely solved with Cholesky, whose symmetry-exploiting economy pays off at large scale.