Contents

LU Factorization

Definition

Definition: Given matrix $A \in \Smxn$ , with $m \leq n$ , its LU factorization is given by where $L \in \Smxn$ is unit lower trapezoidal and $U \in \Snxn$ is upper triangular.

Theorem: Given a matrix $A \in \Smxn$ , $m \leq n$ , its LU factorization exists if every leading principle submatrix of is nonsingular.

The LU factorization is commonly used when solving a square system of linear equations $ A x = b $ where $A \in \Snxn$ and $b \in \Sn$ are given and $x \in \Sn$ is to be computed. If $ A = LU $ , then $A x = b$ means $L U x = b$ or $L y = b$ where $y = U x$ so that $ x $ can be computed by first solving the lower triangular system of equations $ L y = b $ (often referred to as forward substitution) and then solving the upper triangular system $ U x = y $ (often referred to as backward substitution).

$A \becomes LU( A )$ denotes the operation that overwrites

The diagonal of $ L $ , which consists of unit elements, is not stored.

The PME for this operation is given by

$\FlaTwoByTwo{ A_{TL} }{ A_{TR} } { A_{BL} }{ A_{BR} } = \FlaTwoByTwo{ \{ L \backslash U \}_{TL} }{ U_{TR} } { L_{BL} }{ \{ L \backslash U \}_{BR} } $ where $ \left\{ \begin{array}{l @{\hspace{2pt}} l @{\hspace{2pt}} l} \{ L_{TL} \backslash U_{TL} \} & = & LU ( \hat{A}_{TL} ) \\ U_{TR} & =& L_{TL}^{-1} \hat{A}_{TR} \\ L_{BL} & = & \hat{A}_{BL} U_{TL}^{-1} \\ \{ L_{BR} \backslash U_{BR} \} & = & LU( \hat{A}_{BR} - L_{BL} U_{TR}) \end{array} \right.$

Here $A_{TL}, L_{TL}, U_{TL} \in \S^{k \times k}$ .

Details of how to derive the PME for this operation.

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

attachment:LU_with_50.png

LinearAlgebraWiki: LU factorization (last edited 2007-06-01 23:15:56 by MarthaGanser)

Invariant 1	$\FlaTwoByTwo{ A_{TL} }{ A_{TR} } { A_{BL} }{ A_{BR} } = \FlaTwoByTwo{ \{ L \backslash U \}_{TL} }{ \hat{A}_{TR} } { \hat{A}_{BL} }{ \hat{A}_{BR} } $ where $ \hat{A}_{TL} = L_{TL} U_{TL}$
Invariant 2	$\FlaTwoByTwo{ A_{TL} }{ A_{TR} } { A_{BL} }{ A_{BR} } = \FlaTwoByTwo{ \{ L \backslash U \}_{TL} }{ U_{TR} } { \hat{A}_{BL} }{ \hat{A}_{BR} } $ where $ \left\{ \begin{array}{l} \hat{A}_{TL} = L_{TL} U_{TL} \\ L_{TL} U_{TR} = \hat{A}_{TR} \end{array} \right.$
Invariant 3	$\FlaTwoByTwo{ A_{TL} }{ A_{TR} } { A_{BL} }{ A_{BR} } = \FlaTwoByTwo{ \{ L \backslash U \}_{TL} }{ \hat{A}_{TR} } { L_{BL} }{ \hat{A}_{BR} } $ where $ \left\{ \begin{array}{l} \hat{A}_{TL} = L_{TL} U_{TL} \\ L_{BL} U_{TL} = \hat{A}_{BL} \end{array} \right.$
Invariant 4	$\FlaTwoByTwo{ A_{TL} }{ A_{TR} } { A_{BL} }{ A_{BR} } = \FlaTwoByTwo{ \{ L \backslash U \}_{TL} }{ U_{TR} } { L_{BL} }{ \hat{A}_{BR} } $ where $ \left\{ \begin{array}{l} \hat{A}_{TL} = L_{TL} U_{TL} \\ L_{TL} U_{TR} = \hat{A}_{TR} \\ L_{BL} U_{TL} = \hat{A}_{BL} \end{array} \right.$
Invariant 5	$\FlaTwoByTwo{ A_{TL} }{ A_{TR} } { A_{BL} }{ A_{BR} } = \FlaTwoByTwo{ \{ L \backslash U \}_{TL} }{ U_{TR} } { L_{BL} }{ \hat{A}_{BR} - L_{BL} U_{TR} } $ where $ \left\{ \begin{array}{l} \hat{A}_{TL} = L_{TL} U_{TL} \\ L_{TL} U_{TR} = \hat{A}_{TR} \\ L_{BL} U_{TL} = \hat{A}_{BL} \end{array} \right.$