5.4.3 Die Red-Black-Gauß-Seidel-Iteration

Next: 5.4.4 Das parallele Verfahren Up: 5.4 Das Gauß-Seidel Verfahren Previous: 5.4.2 Datengraph der Gauß-Seidel-Iteration

5.4.3 Die Red-Black-Gauß-Seidel-Iteration

Um trotz der ungünstigen Datenabhängigkeiten das Gauß-Seidel-Verfahren auf Vektor- und Parallelrechnern nutzen zu können, teilt man die Indizes der Vektoren in (mindestens) zwei disjunkte Teilmengen $\omega_{\mathrm{red}}$ und $\omega_{\mathrm{black}}$ auf, so daß gilt $K_{i,j}\equiv 0\;\forall i\neq j \in \omega_{\mathrm{red}}$ und analog für $\omega_{\mathrm{black}}$ , d.h. innerhalb der Teilmengen existieren keine Datenabhängigkeiten.
Dann läßt sich der Updateschritt in Alg. 5.7 umformulieren zu
$\begin{algorithmus}% latex2html id marker 17180 [H]\caption{Updateschritt im Red... ...u}_{\mathrm{black}}^{k-1} \right) \\ \end{array} \end{array}$\end{algorithmus}$
Der entsprechende Datengraph ist in Abb. 5.3 dargestellt.

**Abbildung 5.3:** Datengraph der Red-Black-Gauß-Seidel-Iteration
$\begin{figure} \unitlength0.035\textwidth \mbox{}\hfill \begin{picture} (14,1... ..., j-1} \in \omega_{\mathrm{red}}$ }} % \end{picture}\hfill\mbox{} \end{figure}$

Da innerhalb der ''roten'' und ''schwarzen Daten'' keine Abhängigkeiten mehr existieren, ist Algorithmus 5.8 nunmehr leicht vektorisierbar (mit Stride 2 !!). Diese knotenweise Red/Black-Datenaufteilung funktioniert unter bestimmten Umständen (5-Punkte Differenzenstern bei Diskretisierung auf gleichmäßigem Gitter), auch in 2D (wieviele Farben mindestens in 3D ? $\Longrightarrow$ 2 !).

Für die Parallelisierung empfiehlt sich eine Blockvariante obiger Iteration, in welcher die Bearbeitung ''gleichfarbiger'' Datenblöcke keinerlei Kommunikation erfordert. Beim Einheitsquadrat ergibt sich eine schachbrettartige Einfärbung des Gebietes (hier reichen im günstigsten Fall 2 Farben in 2D !!), welche mit der disjunkten Datenaufteilung in Abschnitt 4.3.2 konform geht.

Gundolf Haase
1998-12-22