•

Contents

# 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