=================
Rank-1 Update GER                                                       [TOC]
=================

Für eine $m \times n$ Matrix $A$ und Vektoren $x$ und $y$ soll
mit der Funktion `dger` (double general matrix rank-1 update)
die Operation

---- LATEX -----------------------------------------------------------
A \leftarrow A + \alpha \; x \; y^T
----------------------------------------------------------------------

durchgeführt werden.  Die Matrix $A$ soll also mit

---- LATEX -----------------------------------------------------------
Z := A + \alpha \; x \; y^T
----------------------------------------------------------------------

überschrieben werden.  Dazu werden wir zwei Varianten herleiten.  In beiden
Varianten wird die Operation wieder iterativ mit Zwischenergebnissen

---- LATEX -----------------------------------------------------------
A = A^{(0)}
\leadsto A^{(1)}
\leadsto
\dots A^{(n)} = Z
----------------------------------------------------------------------

ausgeführt.


- In der ersten Variante (Row-Major) betrachten wir die Partitionierung

  ---- LATEX -----------------------------------------------------------
  \left(\begin{array}{c}
        Z_0 \\
        \hline
        Z_k
        \end{array}\right)
  :=
  \left(\begin{array}{c}
        A_0 \\
        \hline
        A_k
        \end{array}\right)
  +
  \alpha
  \left(\begin{array}{c}
        x_0 \\
        \hline
        x_k
        \end{array}\right)
  y^T
  =
  \left(\begin{array}{c}
        A_0 + \alpha\;x_0 y^T \\
        \hline
        A_k + \alpha\;x_k y^T
        \end{array}\right)
  ----------------------------------------------------------------------

  Als Invariante legen wir fest, dass

  ---- LATEX -----------------------------------------------------------
  A^{(k)} =
  \left(\begin{array}{c}
        A_0 + \alpha\;x_0 y^T \\
        \hline
        A_k
        \end{array}\right)
  ----------------------------------------------------------------------

  gelten muss.

- In der zweiten Variante (Col-Major) betrachten wir die Partitionierung

  ---- LATEX -----------------------------------------------------------
  \left(\begin{array}{c|c}
        Z_0 & Z_k
        \end{array}\right)
  :=
  \left(\begin{array}{c|c}
        A_0 & A_k
        \end{array}\right)
  +
  \alpha\;x
  \left(\begin{array}{c|c}
        y_0 & x_k
        \end{array}\right)
  =
  \left(\begin{array}{c|c}
        A_0 + \alpha\;x y_0^T & A_k + \alpha\;x y_k^T
        \end{array}\right)
  ----------------------------------------------------------------------

  Als Invariante legen wir fest, dass

  ---- LATEX -----------------------------------------------------------
  A^{(k)} =
  \left(\begin{array}{c|c}
        A_0 + \alpha\;x y_0^T & A_k
        \end{array}\right)
  ----------------------------------------------------------------------

  gelten muss.


Row-Major (Unblocked)
=====================

Formal kann wieder die gemeinsame Partitionierung von $A^{(k)}$ und $A^{(k+1)}$
betrachtet werden.  Diese liefert:

- Für $A^{(k)}$ gilt:

  ---- LATEX -----------------------------------------------------------
  A^{(k)}
  =
  \left(\begin{array}{c}
        A_0^{(k)} \\
        \hline
        {a_{k}^{(k)}}^T \\
        \hdashline
        A_{k+1}^{(k)}
        \end{array}\right)
  =
  \left(\begin{array}{c}
        A_0 + \alpha\;x_0 y^T \\
        \hline
        a_{k}^T \\
        \hdashline
        A_{k+1}
        \end{array}\right)
  ----------------------------------------------------------------------

- Für $A^{(k+1)}$ soll gelten:

  ---- LATEX -----------------------------------------------------------
  A^{(k+1)}
  =
  \left(\begin{array}{c}
        A_0^{(k+1)} \\
        \hdashline
        {a_{k}^{(k+1)}}^T \\
        \hline
        A_{k+1}^{(k+1)}
        \end{array}\right)
  =
  \left(\begin{array}{c}
        A_0 + \alpha\;x_0 y^T \\
        \hdashline
        a_{k}^T + \alpha\;x_k y^T \\
        \hline
        A_{k+1}
        \end{array}\right)
  ----------------------------------------------------------------------

Das ergibt den Algorithmus:

---- BOX -------------------------------------------------------------
- For $k=0, \dots, n-1$:

  - $a_k^T \leftarrow a_{k}^T + \alpha\;x_k y^T$ (AXPY)

----------------------------------------------------------------------


Col-Major (Unblocked)
=====================

Analog leitet man

---- BOX -------------------------------------------------------------
- For $k=0, \dots, n-1$:

  - $a_k \leftarrow a_{k} + \alpha\;x y_k$ (AXPY)

----------------------------------------------------------------------

her mit

---- LATEX -----------------------------------------------------------
A =
\left(\begin{array}{c|c|c}
      A_{0} & a_k & A_{k+1}
      \end{array}\right).
----------------------------------------------------------------------


Aufgabe
=======

Implementiert beide Varianten.  Im Fall $\alpha=0$ oder $m=0$ oder
$n=0$ soll ein Quick-Return erfolgen.

:import: session06/example01/bench_ger.c



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