Cholesky Decomposition

Numerical Analysis · Axiom Academy

Efficient factorization for symmetric positive definite matrices For symmetric positive definite (SPD) matrices, we can do better than LU decomposition. The Cholesky decomposition factors A as: where L is a lower triangular matrix with positive diagonal entries. This is like LU, but U = Lᵀ, so we only need to compute one triangular matrix! Symmetric Positive Definite Matrices A matrix A is symmetric positive definite if: Covariance matrices in statistics Stiffness matrices in finite element analysis Gram matrices (AᵀA for any matrix A with full column rank) Hessians of strictly convex functions We compute L column by column, using these formulas: Works for any matrix Stores L and U separately ~⅔n³ operations Needs pivoting for stability Only for SPD matrices Only stores L (half the storage!) ~⅓n³ operations (2× faster!) No pivoting needed! What: A = LLᵀ for SPD matrices When: Matrix is symmetric and positive definite Why: Half the storage, twice as fast, inherently stable How: Compute L column by column using the formulas You've learned Cholesky decomposition - the best method for SPD matrices!

This is the written version of the interactive lesson above. See the full Numerical Analysis course.