6.3.1 Parallelisierung mittels zyklischer Reduktion

Zyklische Reduktion :  
Umordnung der Gleichungen und Unbekannten derart, daß mehrere Unbekannte gleichzeitig (parallel) eliminiert werden können.

Grundidee der Umordnung für $N\,=\,2^3-1\,=\,7$ Unbekannte

Eliminiere alle $x_i$ mit $i \mod 2 = 1$ aus dem GlS :

$$\begin{array}{ccccccccccccc} b_1 x_1 &+& c_1 x_2 &&&&&&&& &=&... ...7 &=& f_6 \\ &&&&&&&& a_6 x_6 &+& b_7 x_7 &=& f_7 \end{array}$$

$\Longrightarrow$ $\begin{array}[t]{ccccccc} \widetilde{b} \makebox[0pt]{}_2 x_2 &+& \widetilde{c... ...de{b} \makebox[0pt]{}_6 x_6 &=& \widetilde{f} \makebox[0pt]{}_3 \\ \end{array}$

Eliminiere alle $x_i$ mit $i \mod 4 = 2$ $\Longrightarrow$ $\widehat{b} \makebox[0pt]{}_4 x_4 \,=\, \widehat{f} \makebox[0pt]{}_4$


Allg.:

 

Der in Bild 6.6 dargestellte Eliminationsbaum (und damit die zyklische Reduktion)

• benötigt doppelt so viel Arithmetik wie die normale Gaußelimination, aber
• ist parallel abarbeitbar.
• Eine sequentielle Umordnung zur Fill-In Reduktion hat keinerlei Bedeutung für die parallele Abarbeitung.

Bemerkung : Es gibt es für die Parallelisierung direkter Verfahren für dünnbesetzte (sparse )Matrizen kein generelles Konzept !