6.3 Matrix-Vektor-Multiplikation im Ring

Eine n × n -Matrix A soll multipliziert werden mit einem n × 1 -Vektor x , d.h., gesucht ist y = Ax . Die Matrix A und der Vektor x seien zeilenweise in Blockstreifen verteilt. Nach einem initialen All-to-All zum Verteilen des Vektors kann jeder Prozessor seinen Teil des Ergebnisvektors y bestimmen.

Im Ring benötigt All-to-All von Paketen der Größe n/p zwischen p Prozessoren O(n) Zeit. Die Multiplikation von ${\frac{n}{p}}$ Zeilen von Matrix A mit dem Vektor x benötigt zusätzlich O(${\frac{n^2}{p}}$) . Die Gesamtzeit beträgt daher O(n + ${\frac{n^2}{p}}$) = O(${\frac{n^2}{p}}$) bei p Prozessoren. Also ist der Algorithmus kostenoptimal für p $\leq$ n .