Cholesky Decomposition: Efficient Symmetric Matrix Factorization for Numerical Computing
Compute Cholesky decompositions step by step. Learn how positive definite matrices factor into LL^T, and why Cholesky is faster than LU for symmetric systems.
Cholesky decomposition is a specialized matrix factorization that decomposes a symmetric, positive-definite matrix A into the product of a lower triangular matrix L and its transpose: A = LL^T. Named after André-Louis Cholesky, a French military officer and mathematician who developed the method for solving geodetic survey problems, this decomposition is approximately twice as efficient as general LU decomposition and is the method of choice for symmetric positive-definite systems.
A matrix is positive-definite if x^T Ax > 0 for every non-zero vector x. This property ensures that all eigenvalues are positive and that the Cholesky factorization exists and is unique. Positive-definite matrices arise naturally in covariance matrices (statistics), stiffness matrices (structural engineering), and Gram matrices (machine learning).
Core Formula
A = LL^T
L_ij = (A_ij - Σ(k=1 to j-1) L_ik × L_jk) / L_jj (for i > j)
L_ii = √(A_ii - Σ(k=1 to i-1) L_ik²)
The Algorithm: Column by Column
The Cholesky algorithm computes L column by column from left to right. For the first column, L_i1 = A_i1 / L_11. For subsequent columns, each entry is computed by subtracting the dot product of previously computed L entries and dividing by the diagonal element. The diagonal elements are square roots of the adjusted diagonal values, which is why the matrix must be positive-definite (negative values under the square root indicate the matrix is not positive-definite).
Computational Advantages
Cholesky decomposition requires approximately n³/3 floating-point operations, compared to 2n³/3 for LU decomposition. This 2x speed advantage, combined with the guarantee of numerical stability without pivoting, makes Cholesky the preferred method for solving large symmetric positive-definite systems. It is also used as a building block in simulating multivariate normal distributions in statistics.
Applications
- Monte Carlo Simulation: Generating correlated random variables uses Cholesky factors of covariance matrices.
- Optimization: Newton's method in constrained optimization requires solving systems with positive-definite Hessian matrices.
- Finite Element Analysis: Stiffness matrices in structural mechanics are symmetric positive-definite and efficiently solved via Cholesky.
- Statistics: Bayesian inference and Gaussian process regression use Cholesky decomposition for efficient covariance matrix operations.
Key Takeaway
Cholesky decomposition factors a symmetric positive-definite matrix A into LL^T. It is twice as fast as LU decomposition, numerically stable without pivoting, and essential for simulation, optimization, and statistical computing. The algorithm fails gracefully if the matrix is not positive-definite.