7.2 Gauß-Elimination im Gitter

Idee:

In Phase k wird ein geeignetes Vielfaches der Zeile k von allen Zeilen unterhalb von k subtrahiert, so daß die Spalte k unterhalb von k zu Null wird. Ergebnis ist eine obere Dreiecksmatrix D und Vektor c , deren Lösung Dx = c auch Ax = b löst.

Die sequentielle Version lautet:

FOR k = 0 TO n-1 DO (* Phase k *)
   FOR j := k+1 TO n DO (* Division *)
      a[k,j] := a[k,j]/a[k,k]
   END
   a[k,k] := 1;
   FOR i := k+1 TO n-1 DO
      FOR j := k+1 TO n DO (* Elimination *)
         a[i,j] := a[i,j] - a[i,k] * a[k,j]
      END
      a[i,k] := 0;
   END
END

Gelöst wird Dx = c durch das sukzessive Auflösen der jeweils letzten Zeile und Rückwärtseinsetzen der Lösung. Dieses Verfahren wird Backsubstitution genannt.

Es wird ein MC ² verwendet, bei dem die lokale Variable des Prozessors P_ij mit dem Matrixelement a_ij initialisiert wird. Der Eliminationsschritt kann umformuliert werden als

a[i,j] := a[i,j] - a[i,k] * a[k,j]/a[k,k]

An der Modifikation von a_ij beteiligte Matrixelemente

Die k -te Phase wird gestartet durch Prozessor P_kk , der seinen momentanen Wert a_kk nach rechts schickt zu P_{k,k + 1},P_{k,k + 2},...,P_k,n und seinen Wert a_kk dann auf 1 setzt. Jeder Prozessor P_kj,j > k , dividiert nach Erhalt von a_kk sein a_kj durch a_kk und kann dann sein modifiziertes a_kj nach unten schicken. Prozessor P_ij , der von oben einen Wert b und von links einen Wert c erhalten hat, reicht diese nach unten resp. nach rechts weiter und subtrahiert das Produkt von seinem lokalen Matrixelement, d.h., er bildet

Alle Phasen laufen in Pipeline-Manier überlappend, d.h., Phase k + 1 wird von P_{k + 1, k + 1} eingeleitet, sobald alle für P_{k + 1,k + 1} bestimmten Nachrichten eingetroffen sind.

Pipeline Gauß-Elimination

Da jede Phase O(n) Schritte dauert und zwischen zwei Phasenstarts konstante Zeit liegt, beträgt die Gesamtlaufzeit O(n) . Bei n ² Prozessoren entstehen Kosten von O(n ³) . Der Algorithmus ist daher kostenoptimal.
In Anschluß daran findet eine Backsubstitution statt.