FOR ALL
0 i n - 1 DO IN PARALLEL
Pi : tmp[i] := y[i]
END
FOR j := n-1 DOWNTO 0 DO
FOR ALL
0 i j DO IN PARALLEL
Pi : 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
= 250 ).
Permutiere A so, daß alle Nicht-Null-Einträge nahe
der Hauptdiagonale sind.
Haben die Nicht-Null-Einträge den maximalen Abstand von der
Hauptdiagonale, so hat A
die Bandbreite
2 · .
Dann hat Matrix U mit
U T · U = A die Bandbreite .
Also schränkt sich der Indexbereich ein:
Zur parallelen Cholesky-Zerlegung einer dünn besetzten Matrix mit Bandbreite werden p < Prozessoren im Ring verwendet. Idee: Verteile die Spalten von A nach Round-Robin auf die Prozessoren. Rechne nur innerhalb der Skyline.
Cholesky-Zerlegung mit p = 3 Prozessoren. | |
Markiert sind drei Elemente der 9. Zeile, | |
die gleichzeitig bestimmt werden können. |