4.1.2 Matrix-Vektor Operationen (BLAS2)

In diesem Abschnitt werden nur vollbesetzte Matrizen, bzw. Matrizen mit Bandstruktur betrachtet.

Arten der Matrixspeicherung bei vollbesetzter Matrix $A$.

1.

zeilenweise (row storage) [C,Pascal]

2.

spaltenweise (column storage) [F77]

3.

$A \,=\, A^T$ : zeilenweise oberes Dreieck $A_U$

4.

$A \,=\, A^T$ : spaltenweise unteres Dreieck $A_L$

Aufgabe :

Stellen Sie die Operation $\underline{{\ensuremath{\color{green} {\sf v}} }} \,=\, A_{n\times n} \underline{{\ensuremath{\color{green} {\sf x}} }}$ mittels BLAS-Routinen ( DDOT, DAXPY) für die Speicherformen i)-iii) dar.
$\ast$ Fall ii) ohne BLAS aber mit loop unrolling (Stride 2).




Für die tridiagonale Matrix $$A \,=\, \begin{pmatrix}b_1 & c_1 \\ a_1 & b_2 & c_2 \\ ... ... \\ & & & & c_{n-1} \\ & & & a_{n-1}& b_n \end{pmatrix}$$
betrachten wir 2 Varianten der Matrix-Vektor Multiplikation $\underline{{\ensuremath{\color{green} {\sf v}} }} \,=\, A_{n\times n} \underline{{\ensuremath{\color{green} {\sf x}} }}$ auf dem Vektorrechner.

Variante a) Die Matrix wird in den Vektoren $a(1:n-1)$, $b(1:n)$, $c(1:n-1)$ gespeichert.

    $v_1 \;=\; b_1 \ast x_1 + c_1 \ast x_2$

    $v_n \;=\; b_n \ast x_n + a_{n-1} \ast x_{n-1}$


DO $i\,=\,2,\,n-1$

		    $y_i \;=\; a_{i-1} \ast x_{i-1} + b_i \ast x_i + c_i \ast x_{i+1}$


END DO

Variante b) Gegenüber Variante a) werden die Vektoren $a,c,x$ verlängert :
$a(0:n-1)$, $b(1:n)$, $c(1:n), x(0:n+1)$.

    $x_0 \;=\; x_{n+1} \;=\;0$

    $a_0 \;=\; c_n \;=\;0$


DO $i \,=\, 1,\, n$

		     $y_i \;=\; a_{i-1} \ast x_{i-1} + b_i \ast x_i + c_i \ast x_{i+1}$


END DO

In Variante a) müssen die ersten beiden Zeilen seriell abgearbeitet werden, was bei Vektorrechnern eine Geschwindigkeitseinbuße um das 5- 15-fache bedeutet. Daher ist Variante b) auf dem Vektorrechner schneller, obwohl mehr arithmetische Operationen ausgeführt werden müssen.