===========================================
Ungeblockte LU-Zerlegung ohne Pivotisierung                     [TOC]
===========================================

Für eine diagonaldominante $m \times n$ Matrix $A$ soll die
LU-Zerlegung berechnet werden.  Wir betrachten dabei wieder
die Partitionierung

---- LATEX -------------------------------------------------------------
A =
\left(\begin{array}{c|c|c}
      A_{0,0}   & a_{0,j}   & A_{0,j+1} \\
      \hline
      a_{j,0}^T & a_{j,j}   & a_{j,j+1}^T \\
      \hline
      A_{j+1,0} & a_{j+1,j} & A_{j+1,j+1} \\
      \end{array}\right)
------------------------------------------------------------------------

Die Herleitung der Varianten erfolgt wie in der Volesung gezeigt wurde.


LU-Variante 1
=============


---- BOX -------------------------------------------------------------
- For $j=0, \dots, \min\{m,n\}-1$:
   - If j<n
      - $a_{0,j} \leftarrow L_1(A_{0,0})^{-1} a_{0,j}$
   - If j<m
      - $a_{j,0} \leftarrow U(A_{0,0})^{-T} a_{j,0}$
   - If j<m and j<n
      - $a_{j,j} \leftarrow a_{j,j} - a_{j,0}^T a_{0,j}$
----------------------------------------------------------------------


LU-Variante 2
=============

---- BOX -------------------------------------------------------------
- For $j=0, \dots, \min\{m,n\}-1$:
   - If j<m
      - $a_{j,0} \leftarrow U(A_{0,0})^{-T} a_{j,0}$
   - If j<n
      - $a_{j,j}   \leftarrow a_{j,j}   - a_{0,j}^T a_{j,0}$
      - $a_{j,j+1} \leftarrow a_{j,j+1} - A_{0,j+1}^T a_{j,0}$
----------------------------------------------------------------------

LU-Variante 3
=============

---- BOX -------------------------------------------------------------
- For $j=0, \dots, \min\{m,n\}-1$:
   - If j<n
      - $a_{0,j} \leftarrow L_1(A_{0,0})^{-1} a_{0,j}$
   - If j<m
      - $a_{j,j} \leftarrow a_{j,j} - a_{j,0}^T a_{0,j}$
   - If j+1<m
      - $a_{j+1,j} \leftarrow \frac{1}{a_{j,j}}\left(a_{j+1,j} - A_{j+1,0} a_{0,j}\right)$
----------------------------------------------------------------------

LU-Variante 4
=============

---- BOX -------------------------------------------------------------
- For $j=0, \dots, \min\{m,n\}-1$:
   - $a_{j,j}   \leftarrow a_{j,j}   - a_{0,j}^T a_{j,0}$
   - $a_{j,j+1} \leftarrow a_{j,j+1} - A_{0,j+1}^{T} a_{j,0}$
   - If j+1<m
      - $a_{j+1,j} \leftarrow \frac{1}{a_{j,j}}\left(a_{j+1,j} - A_{j+1,0}^T a_{0,j}\right)$
----------------------------------------------------------------------

Hier nützt man natürlich aus, dass dann

---- LATEX -----------------------------------------------------------
\left(\begin{array}{c}
      a_{j,j} \\
      \hline
      a_{j,j+1}
      \end{array}\right)
=
\left(\begin{array}{c}
      a_{j,j} \\
      \hline
      a_{j,j+1}
      \end{array}\right)
-
\left(\begin{array}{c}
      a_{0,j} \\
      \hline
      A_{0,j+1}
      \end{array}\right)^T
a_{j,0}
----------------------------------------------------------------------

mit einer GEMV-Operation berechnte werden kann.

LU-Variante 5
=============

---- BOX -------------------------------------------------------------
- For $j=0, \dots, \min\{m,n\}-1$:
   - $a_{j+1,j}   \leftarrow \frac{1}{a_{j,j}} a_{j+1,j}$
   - $A_{j+1,j+1} \leftarrow A_{j+1,j+1} - a_{j+1,j} a_{j,j+1}^T$
----------------------------------------------------------------------



Aufgabe
=======

- Ergänzt die Vorlage
- Verwendet verschiedene Optimierungen
- Testet die Implementierung für zeilen- und splatenweise gespeicherte Matrizen
- Testet die Implementierung für nicht-quadratische Matrizen

:import: session06/example01/bench_lu_unblk.c


:navigate: up    -> doc:index
           next  -> doc:session06/page06
           back  -> doc:session06/page04