Flame Logo

Contents

  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

        

means

        

or

        

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).


Algorithms

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.

Loop-invariants

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

Invariant 1

Invariant 2

 



Related Operations