7.1 Gauß-Jordan-Elimination auf PRAM

Idee:

In Phase k wird ein geeignetes Vielfaches der Zeile k von allen anderen Zeilen subtrahiert, so daß die Spalte k (bis auf a_kk ) zu Null wird. Ergebnis ist eine Diagonalmatrix. Der zentrale Schritt lautet daher

Es wird eine PRAM mit n(n + 1) Prozessoren verwendet, wobei in Phase k Prozessor P_ij die Elemente a[i,j] und a[k,j] verknüpft.

FOR k := 0 TO n-1 DO
     FOR ALL 0 $\leq$ i < n,k $\leq$ j $\leq$ n,i $\neq$ k DO IN PARALLEL
             P_ij : a[i,j] := a[i,j] - (a[i,k]/a[k,k])* a[k,j]
     END
END
FOR ALL 0 $\leq$ i $\leq$ n - 1 DO IN PARALLEL
     P_in : x[i] := a[i,n]/a[i,i]
END

Bei O(n ²) Prozessoren entstehen O(n ³) Kosten, also ist der Algorithmus kostenoptimal.