Parallele Backward-Substitution

Prozessor P_i kennt Zeile i von U .

FOR ALL 0 $\leq$ i $\leq$ n - 1 DO IN PARALLEL
     P_i : tmp[i] := y[i]
END
FOR j := n-1 DOWNTO 0 DO
     FOR ALL 0 $\leq$ i $\leq$ j DO IN PARALLEL
         P_i : falls i = j: x[i] := tmp[i]/u[i,i];
                 verschicke x[i];
             falls i < j: erhalte x[j];
                 reiche ggf. weiter;
                 tmp[i] := tmp[i]-u[i,j]*x[j];

Der sequentielle Cholesky-Algorithmus profitiert von dünn besetzten Matrizen, die bei FEM-Verfahren auftreten. Z.B. beträgt bei einem 2D -Problem mit n = 50.000 die Bandbreite etwa $\sqrt{n}$ = 250 ).

Permutiere A so, daß alle Nicht-Null-Einträge nahe der Hauptdiagonale sind. Haben die Nicht-Null-Einträge den maximalen Abstand $\Delta$ von der Hauptdiagonale, so hat A die Bandbreite 2 · $\Delta$ . Dann hat Matrix U mit U ^T · U = A die Bandbreite $\Delta$ .

Also schränkt sich der Indexbereich ein:

Zur parallelen Cholesky-Zerlegung einer dünn besetzten Matrix mit Bandbreite $\Delta$ werden p < $\Delta$ Prozessoren im Ring verwendet. Idee: Verteile die Spalten von A nach Round-Robin auf die Prozessoren. Rechne nur innerhalb der Skyline.