Flame Logo


  1. Cholesky Factorization
    1. When is it a legal operation?
    2. How is it used?
  2. Algorithms
    1. Partitioned Matrix Expression
    2. Loop-invariants
    3. Algorithmic variants
    4. Performance

Cholesky Factorization

Given a matrix its Cholesky factorization is given by where is LowerTriangular. Matrix is called the Cholesky factor of matrix .

When is it a legal operation?

Cholesky Factorization Theorem: Let be a SymmetricPositiveDefinite matrix. Then there exists a LowerTriangular matrix such that . If the diagonal of is taken to be positive, the factorization is unique.

How is it used?

The Cholesky factorization is commonly used when solving a square SystemOfLinearEquations where SymmetricPositiveDefinite matrix and are given and is to be computed. If , then






so that can be computed by first solving the LowerTriangularSystem of equations (often referred to as ForwardSubstitution) and then solving the UpperTriangularSystem (often referred to as BackwardSubstitution).


denotes the operation that overwrites the Lowertriangular part of with the LowerTriangular matrix .

Partitioned Matrix Expression

The PME for this operation is given by


Details of how to derive the PME for this operation.


The dependencies in the above PME allow for three different loop-invariants to be identified:

Invariant 1

Invariant 2


Related Operations