Skip to content
Algorithm Atlas
Numerical MethodsAll categories
CoreSource checked

Cholesky Decomposition

Factors a symmetric positive definite matrix into a triangular matrix and its transpose.

Explore relationshipsOpen constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Numerical Methods
Difficulty
Intermediate
Family
Matrix Factorization
Tier
Core
Status
Verified
Review
Source Checked
Sources
1
Formulas
1
Relationships
2
Code example
Ready
Visualization
Ready

Overview

Cholesky Decomposition is a fast and stable way to solve systems when the matrix has the required symmetry and positivity.

Core Concepts

symmetric matrixpositive definitetriangular factorlinear solve

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n^3)

Average

O(n^3)

Worst

O(n^3)

Space

O(n^2)

When to Use

  • Use when the matrix is symmetric positive definite and repeated solves are needed.
  • Use when least-squares solvers is a central requirement.

When Not to Use

  • Avoid when the matrix is indefinite, nonsymmetric, or poorly conditioned.
  • Avoid when roundoff, conditioning, or discontinuities dominate the result.

What It Does

  • Checks or assumes positive definiteness
  • Builds a lower triangular factor
  • Solves systems with forward and backward substitution

Use Cases

  • Least-squares solvers
  • Gaussian process models
  • Covariance matrix operations

Inputs

  • Symmetric positive definite matrix

Outputs

  • Lower triangular factor

Key Formulas (1)

Cholesky factorization

A = L · LT
A = L * L^T

Factors a suitable matrix into a lower triangular matrix and its transpose.

Pseudocode

  1. 1.Process rows and columns in order
  2. 2.Compute each diagonal value from remaining variance
  3. 3.Compute lower-triangular off-diagonal values
  4. 4.Use the factor for solves or determinant calculations

Canonical Example

Input
A = [[4, 2], [2, 3]]
Output
A = L * L^T
Explanation
The matrix can be solved through two triangular substitutions.

Implementation Notes

  • Use library routines that report factorization failure cleanly.
  • Compare against a small hand-checkable case before scaling up.
  • Keep a tiny example with expected output beside the implementation.

Common Pitfalls

  • Tiny negative diagonal terms may indicate numerical or modeling issues.
  • Ignoring conditioning can make a correct method return unreliable numbers.
  • Not defining boundary, empty, or degenerate inputs before implementation.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show a symmetric matrix splitting into a triangular factor times its transpose.

Cholesky Decomposition mechanism walkthrough step 1 of 4x₀x₁x₂x*
Step 1 of 4: Process rows and columns in order
numeric-iteration

Notes

The factorization fails if the matrix is not positive definite.

Sources (1)

What each reference supports for this entry.

Matrix Computations

Book

Reference text for numerical linear algebra, matrix factorizations, SVD, and eigenvalue methods.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Often paired withConjugate Gradient

Numerical Methods · Extended

Both are important for positive definite linear systems.

Compare with this
SpecializesLU Decomposition

Numerical Methods · Core

Cholesky is a specialized factorization for symmetric positive definite matrices.

Compare with this

Relationships

View full relationship page
Often paired withConjugate Gradient

Both are important for positive definite linear systems.

SpecializesLU Decomposition

Cholesky is a specialized factorization for symmetric positive definite matrices.

Related Algorithms

LU DecompositionGaussian Elimination

Tags

Numerical MethodsLinear AlgebraDecomposition