LU-factorization

Algorithm

1.
If a₁₁ = 0, fail!
2.
If n = 1, return L = 1 and U = a₁₁.
3.
Write A as $\begin{eqnarraystar} A \; = \; \left[ \begin{array} {c\vert ccc} a_{11} & a_{1... ...n{array} {cc} a_{11} & r^T \ c & A' \end{array} \right], \end{eqnarraystar}$
4.
Define $A_1 = A' - \displaystyle \frac{c \cdot r^T}{a_{11}}$ . (Schur complement, see CLR p.755)
5.
Recursively compute the LU-factorization of A₁ A₁ & = & L₁ U₁
6.
Return $\begin{eqnarraystar} L \; = \; \left[ \begin{array} {cc} 1 & 0 \ c/a_{11} & ... ...n{array} {cc} a_{11} & r^T \ 0 & U_1 \end{array} \right] \end{eqnarraystar}$
Correctness of the algorithm
- Show $L \cdot U = A$
  
  1.
  Base case -- $L \cdot U = 1 \cdot a_{11} = a_{11} = A$
  2.
  Otherwise -- $\begin{eqnarraystar} L \cdot U & = & \left[ \begin{array} {cc} 1 & 0 \ c/a_{... ...c} a_{11} & r^T \ c & A' \end{array} \right] \ & = & A \end{eqnarraystar}$
- Show L is lower-triangular and U is upper-triangular (Exercise)
- Termination: # recursive calls $= n \! - \! 1$
Operation count
- Computing A₁ (Schur complement) costs $\Theta(n^2)$ operations
- $T(n) = T(n-1) + \Theta(n^2)$
- Solution?

Next: PLU-factorization Up: SOLVING LINEAR SYSTEMS Previous: Expressing the Algorithm