Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


36. Arithmetik



Rechenoperationen mit Matrizen

Die Implementation der grundlegenden Rechenoperationen für Matrizen erfordert Überlegungen, die den oben für Polynome angestellten ähnlich sind. Zum Beispiel ist die Addition zweier Matrizen trivial, da sie, genau wie Polynome, einfach Term für Term addiert werden.

Die Multiplikation von Matrizen ist ebenfalls sehr einfach. Falls r das Produkt von p und q ist, so ist das Element r[i,j] das Skalarprodukt der i-ten Zeile von p mit der j-ten Spalte von q. Das Skalarprodukt ist einfach die Summe der N Produkte der Elementenpaare p[i,0] * q[0,j] + p[i,1] * [1,j] + p[i,2] * [2,j] + ... + p[i,N-1] * q[N - 1,j], wie im folgenden Programm:

    for i:=0 to N-1 do
      for j:=0 to N-1 do
        begin
        t:=0.0;
        for k:=0 to N-1 do t:=t+p[i,k]*q[k,j];
        r[i,j]:=t
        end;

Für die Überprüfung des obigen Programmabschnitts könnte der Leser das folgende Beispiel benutzen:

Formel

Jedes der N2 Elemente in der resultierenden Matrix wird mit Hilfe von N Multiplikationen berechnet, so daß ungefähr N3 Operationen erforderlich sind, um zwei NxN-Matrizen miteinander zu multiplizieren.

Wie im Falle von Polynomen können lichte Matrizen (solche, bei denen viele Elemente den Wert null haben) in einer wesentlich effizienteren Weise verarbeitet werden, indem eine Darstellung mit Hilfe verketteter Listen verwendet wird. Um die zweidimensionale Struktur zu erhalten, wird jedes von null verschiedene Element der Matrix durch einen Listenknoten dargestellt, der einen Wert und zwei Verbindungen enthält, von denen eine auf das nächste von null verschiedene Element in der gleichen Zeile und die andere auf das nächste von null verschiedene Element in der gleichen Spalte zeigt. Die Implementation der Addition für in dieser Weise dargestellte lichte Matrizen ist unserer Implementation für lichte Polynome ähnlich, wird jedoch durch die Tatsache erschwert, daß jeder Knoten in zwei Listen erscheint.

Die bekannteste Anwendung des Prinzips »Teile und Herrsche« auf ein arithmetisches Problem ist die Methode von Strassen für die Multiplikation von Matrizen. Wir wollen hier auf keine Einzelheiten eingehen, können jedoch das Verfahren skizzieren, da es von der Idee her der soeben betrachteten Methode der Multiplikation von Polynomen sehr ähnlich ist.

Das herkömmliche Verfahren für die Multiplikation zweier NxN-Matrizen erfordert N3 skalare Multiplikationen, da jedes der N2 Elemente der Ergebnismatrix durch N Multiplikationen erhalten wird. Das Verfahren von Strassen besteht darin, den Umfang des Problems zu halbieren; dies entspricht der Zerlegung jeder der Matrizen in Viertel, jedes vom Typ N/2 mal N/2. Das verbleibende Problem ist zur Multiplikation von 2x2-Matrizen äquivalent. Ebenso wie wir in der Lage waren, bei der Multiplikation von Polynomen die Anzahl der erforderlichen Multiplikationen durch Kombination von Gliedern von vier auf drei zu reduzieren, gelang es Strassen, eine Möglichkeit zu finden, Glieder so zu kombinieren, daß sich die Anzahl der Multiplikationen, die für das Problem der Multiplikation von 2x2-Matrizen erforderlich sind, von 8 auf 7 reduziert. Die Anordnung und die Glieder, die dafür benötigt werden, sind sehr kompliziert.

Eigenschaft 36.2 Zwei NxN-Matrizen können unter Verwendung von ungefähr N2,81 Multiplikationen multipliziert werden.

Aus der obigen Erläuterung folgt, daß die Anzahl der für die Multiplikation von Matrizen erforderlichen Multiplikationen bei Anwendung der Methode von Strassen durch die rekurrente Beziehung vom Typ »Teile und Herrsche«

M(N) = 7M(N/2)

definiert ist, welche die oben angegebene Lösung

M(N) rund Nlg 7 rund N2,81

besitzt. w.z.b.w.

Dieses Ergebnis war sehr überraschend, als es 1968 erstmals veröffentlicht wurde, da zuvor angenommen worden war, daß für die Multiplikation von Matrizen unbedingt N3 Multiplikationen erforderlich sind. Das Problem wurde in den letzten Jahren sehr gründlich untersucht, und es wurden Methoden gefunden, die noch etwas besser sind als die von Strassen. Der »beste« Algorithmus für die Multiplikation von Matrizen ist noch immer nicht gefunden worden, und es handelt sich hier um eines der bekanntesten noch offenen Probleme der Informatik.

Es ist wichtig festzustellen, daß wir nur die Multiplikationen gezählt haben. Bevor ein Algorithmus für eine praktische Anwendung gewählt wird, müssen auch die Kosten der zusätzlichen Additionen und Subtraktionen für die Kombination der Glieder und die Kosten der rekursiven Aufrufe berücksichtigt werden. Diese Kosten können stark von der speziellen Implementation oder vom verwendeten Computer abhängen. Doch dieser zusätzliche Ballast bewirkt auf jeden Fall, daß die Methode von Strassen für kleine Matrizen weniger effizient ist als die standardmäßige Methode. Selbst für große Matrizen, ausgedrückt über die Anzahl der eingegebenen Datenelemente, stellt die Methode von Strassen in Wirklichkeit nur eine Verbesserung von N1,5 auf N1,41 dar. Diese Verbesserung ist kaum spürbar, außer für sehr große N. Zum Beispiel müßte N mehr als eine Million betragen, damit die Anzahl der Multiplikationen bei der Methode von Strassen nur ein Viertel der Anzahl bei der Standardmethode beträgt, obwohl der Ballast pro Multiplikation viermal so groß sein dürfte. Somit ist dieser Algorithmus mehr ein theoretischer als ein praktischer Beitrag.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]