Contents

Cholesky Factorization
1. When is it a legal operation?
2. How is it used?
Algorithms

Cholesky Factorization

Given a matrix $A \in \Snxn$ its Cholesky factorization is given by $ A = L L^T $ where $L \in \Snxn$ is LowerTriangular. Matrix $L$ is called the Cholesky factor of matrix $A$ .

When is it a legal operation?

Cholesky Factorization Theorem: Let $A \in \Snxn$ be a SymmetricPositiveDefinite matrix. Then there exists a LowerTriangular matrix $L \in \Snxn$ such that $ A = L L^T $ . If the diagonal of $L$ is taken to be positive, the factorization is unique.

How is it used?

The Cholesky factorization is commonly used when solving a square SystemOfLinearEquations $ A x = b $ where SymmetricPositiveDefinite matrix $A \in \Snxn$ and $b \in \Sn$ are given and $x \in \Sn$ is to be computed. If $ A = LL^T $ , then

$A x = b$

means

$L L^T x = b$

$L y = b \quad \mbox{where} \quad y = L^T x$

so that $ x $ can be computed by first solving the LowerTriangularSystem of equations $ L y = b $ (often referred to as ForwardSubstitution) and then solving the UpperTriangularSystem $ L^T x = y $ (often referred to as BackwardSubstitution).

Algorithms

$A \becomes \chol( A )$ denotes the operation that overwrites the Lowertriangular part of $ A $ with the LowerTriangular matrix $ L $ .

Partitioned Matrix Expression

The PME for this operation is given by

$\FlaTwoByTwo{ A_{TL} }{ \star } { A_{BL} }{ A_{BR} } = \FlaTwoByTwo{ L_{TL} }{ \star } { L_{BL} }{ L_{BR} } $ where $ \left\{ \begin{array}{l @{\hspace{2pt}} l @{\hspace{2pt}} l} \hat{A}_{TL} & = & L_{TL} L_{TL}^T \\ \hat{A}_{BL} & =& L_{BL} L_{TL}^{-T} \\ \hat{A}_{BR} - L_{BL} L_{BL}^T & = & L_{BR} L_{BR}^T \end{array} \right.$

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

$\FlaTwoByTwo{ A_{TL} }{ \star } { A_{BL} }{ A_{BR} } = \FlaTwoByTwo{ L_{TL} }{ \star } { \hat{A}_{BL} }{ \hat{A}_{BR} } $ where $ \hat{A}_{TL} = L_{TL} L_{TL}^T$

Invariant 2

$\FlaTwoByTwo{ A_{TL} }{ \star } { A_{BL} }{ A_{BR} } = \FlaTwoByTwo{ L_{TL} }{ \star } { L_{BL} }{ \hat{A}_{BR} } $ where $ \left\{ \begin{array}{l @{\hspace{2pt}} l @{\hspace{2pt}} l} \hat{A}_{TL} & = & L_{TL} L_{TL}^T \\ \hat{A}_{BL} & =& L_{BL} L_{TL}^{-T} \end{array} \right.$

Invariant 3

$\FlaTwoByTwo{ A_{TL} }{ \star } { A_{BL} }{ A_{BR} } = \FlaTwoByTwo{ L_{TL} }{ \star } { L_{BL} }{ \hat{A}_{BR} - L_{BL} L_{BL}^T } $ where $ \left\{ \begin{array}{l @{\hspace{2pt}} l @{\hspace{2pt}} l} \hat{A}_{TL} & = & L_{TL} L_{TL}^T \\ \hat{A}_{BL} & =& L_{BL} L_{TL}^{-T} \end{array} \right.$

Algorithmic variants

Variant 1	unb	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 1	blk	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 2	unb	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 2	blk	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 3	unb	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 3	blk	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC

Performance

Enlarge

Try it yourself

attachment:Chol_l_without_50.png

Related Operations

LU factorization

More Information

LinearAlgebraWiki: Cholesky factorization (last edited 2007-06-01 23:15:07 by MarthaGanser)

Invariant 1	$\FlaTwoByTwo{ A_{TL} }{ \star } { A_{BL} }{ A_{BR} } = \FlaTwoByTwo{ L_{TL} }{ \star } { \hat{A}_{BL} }{ \hat{A}_{BR} } $ where $ \hat{A}_{TL} = L_{TL} L_{TL}^T$
Invariant 2	$\FlaTwoByTwo{ A_{TL} }{ \star } { A_{BL} }{ A_{BR} } = \FlaTwoByTwo{ L_{TL} }{ \star } { L_{BL} }{ \hat{A}_{BR} } $ where $ \left\{ \begin{array}{l @{\hspace{2pt}} l @{\hspace{2pt}} l} \hat{A}_{TL} & = & L_{TL} L_{TL}^T \\ \hat{A}_{BL} & =& L_{BL} L_{TL}^{-T} \end{array} \right.$
Invariant 3	$\FlaTwoByTwo{ A_{TL} }{ \star } { A_{BL} }{ A_{BR} } = \FlaTwoByTwo{ L_{TL} }{ \star } { L_{BL} }{ \hat{A}_{BR} - L_{BL} L_{BL}^T } $ where $ \left\{ \begin{array}{l @{\hspace{2pt}} l @{\hspace{2pt}} l} \hat{A}_{TL} & = & L_{TL} L_{TL}^T \\ \hat{A}_{BL} & =& L_{BL} L_{TL}^{-T} \end{array} \right.$