5.2.2 Der parallele GMRES

Bei Algorithmus 5.3 muß man neben den funktionalen Größen $\underline{f}$, $\underline{r}$ und den Funktionswerten $\underline{u}$, $\underline{w}^k$ noch die Vektoren  $\{z_i\}_{i=\overline{1,k+1} \makebox[0pt]{}}$, $\{s_i\}_{i=\overline{1,k+1} \makebox[0pt]{}}$, $\{c_i\}_{i=\overline{1,k+1} \makebox[0pt]{}}$ und die Matrix  $\{h_{i,j}\}_{i,j=\overline{1,k} \makebox[0pt]{}}$ in Betracht ziehen, wobei diese innerhalb des Algorithmus als skalare Größen betrachtet werden. Folgende Parallelisierungsstrategie wird auf den GMRES ohne Vorkonditionierung ($C=I$) angewandt.

  $\mbox{$\bullet$}$

$\underline{f}$, $\underline{r}$ $\rightarrow$ $\underline{{\ensuremath{\color{green} {\sf f}} }}$, $\underline{{\ensuremath{\color{green} {\sf r}} }}$ werden verteilt gespeichert.

  $\mbox{$\bullet$}$

$\underline{u}$, $\underline{w}^k$ $\rightarrow$ $\underline{{\ensuremath{\color{red} \mathfrak{u} } }}$, $\underline{{\ensuremath{\color{red} \mathfrak{w} } }}^k$ werden akkumuliert gespeichert.

  $\mbox{$\bullet$}$

Die skalaren Größen $\{z_i\}_{i=\overline{1,k+1} \makebox[0pt]{}}$, $\{s_i\}_{i=\overline{1,k+1} \makebox[0pt]{}}$, $\{c_i\}_{i=\overline{1,k+1} \makebox[0pt]{}}$ und $\{h_{i,j}\}_{i,j=\overline{1,k} \makebox[0pt]{}}$ werden redundant auf jedem Prozessor lokal gespeichert.

$\Longrightarrow$

Skalarprodukte können mit sehr geringem Kommunikationsaufwand ausgeführt werden (4.7). Matrix-mal-Vektor benötigt keine Kommunikation (4.8).

!!

Die Zuweisung $\underline{{\ensuremath{\color{red} \mathfrak{w} } }}\,:=\,\underline{{\ensuremath{\color{green} {\sf r}} }}$ beinhaltet eine Vektortypumwandlung mittels Akkumulation (4.5) und damit eine Kommunikation über die zu mehreren Prozessen gehörenden Daten.

  $\mbox{$\bullet$}$

Alle Manipulationen an und mit den skalaren Größen $c_i$, $s_i$, $z_i$ und $h_{i,j}$ werden redundant auf allen Prozessoren lokal ausgeführt.

!!

Fast alle DAXPY-Operationen arbeiten mit den gleichen Vektortypen (und skalaren Größen), außer der Operation

$$\underline{{\ensuremath{\color{green} {\sf r}} }} \,:=\, \und... ...erline{{\ensuremath{\color{red} \mathfrak{w} } }}^i \enspace ,$$

welche verschieden Vektortypen enthält. Eine Umwandlung des akkumulierten Vektors  $\underline{{\ensuremath{\color{red} \mathfrak{w} } }}^i$ in einen verteilten ist nach (4.6) aber ohne Kommunikation möglich !

$\Longrightarrow$

Alle DAXPY-Operationen kommen ohne Kommunikation aus.

 
Der resultierende parallele GMRES-Algorithmus 5.4 erfordert in der $k$-ten Iteration (k+1)  ALL/SMALL>_REDUCE-Operationen mit einer reellen Zahl und eine Vektorakkumulation. Durch die notwendige Typumwandlung des Vektors  $\underline{{\ensuremath{\color{red} \mathfrak{w} } }}^i$ kommen noch zusätzlich $k\cdot n$ Multiplikationen hinzu ($n$ - Länge des Vektors  $\underline{{\ensuremath{\color{red} \mathfrak{w} } }}$).

Die Variante GMRES(m), mit Neustart nach $m$ Iterationen, läßt sich völlig analog parallelisieren.