Der Strassen-Algorithmus

Autor: Mark Probst [ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

Der Strassen-Algorithmus

Der Strassen-Algorithmus ist ein rekursiver Algorithmus, der auf dem divide-and-conquer-Prinzip beruht. Dabei wird in zwei Schritten vorgegangen:

Das Problem wird in möglichst gleichgroße Teilprobleme derselben Art wie das Originalproblem aufgeteilt. Diese Teilprobleme können mit demselben Algorithmus unabhängig voneinander gelöst werden.
Die Lösungen der Teilprobleme werden zu einer Lösung der Originalproblems kombiniert.

Diese Aufteilung wird so lange rekursiv wiederholt, bis die Teilprobleme trivial sind und sofort gelöst werden können. Der einfachste Fall der Matrizenmultiplikation ist die Multiplikation zweier 2x2 Matrizen A,B $A= \left( \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right),\qquad B= \left( \begin{array}{cc} b_{11} & b_{12} \\ b_{21} & b_{22} \end{array} \right).$ Definiert man die Hilfsgrößen

p₁ := (a₁₁ + a₂₂) * (b₁₁ + b₂₂)
p₂ := (a₂₁ + a₂₂) * b₁₁
p₃ := a₁₁ * (b₁₂ - b₂₂)
p₄ := a₂₂ * (b₂₁ - b₁₁)
p₅ := (a₁₁ + a₁₂) * b₂₂
p₆ := (a₂₁ - a₁₁) * (b₁₁ + b₁₂)
p₇ := (a₁₂ - a₂₂) * (b₂₁ + b₂₂)

dann gilt für das Produkt $A \cdot B =: C = \left( \begin{array}{cc} c_{11} & c_{12} \\ c_{21} & c_{22} \end{array} \right),$ wie man durch einfaches Nachrechnen leicht bestätigen kann:

c₁₁ = p₁ + p₄ - p₅ + p₇
c₁₂ = p₃ + p₅
c₂₁ = p₂ + p₄
c₂₂ = p₁ + p₃ - p₂ + p₆

Dieser Algorithmus zur Matrizenmultiplikation, der Strassen-Algorithmus, benötigt in diesem Fall sieben Multiplikationen und 18 Additionen bzw. Subtraktionen, während der Standardalgorithmus nur 8 Multiplikationen und 4 Additionen benötigt. Im Fall von von 2x2 Matrizen ist der Strassen-Algorithmus also deutlich unterlegen, jedoch erkannte Strassen, dass die Formeln (5.3) und (5.4) gültig bleiben, wenn die a_ij und b_ij selbst Matrizen sind. Für diesen allgemeinen Fall werden im folgenden die Algorithmen A_m,k, die zwei Matrizen der Ordnung m2^k multiplizieren, durch Induktion über k definiert. Falls n keine gerade Zahl ist, dann berechnet man die letzte Spalte von C nach den üblichen Methoden und wendet das Verfahren auf die verbleibenden Matrizen der Dimension n-1 an.

Definition 5.5.2: A_m,0 sei der Standardalgorithmus zur Matrizenmultiplikation (dieser benötigt m³ Multiplikationen und m²(m-1) Additionen). Ist A_m,k bereits bekannt, dann sei A_m,k+1 wie folgt definiert:

Sollen die Matrizen A und B der Ordnung m2^k+1 multipliziert werden, dann unterteilt man A, B und A.B in Blöcke

$A= \left( \begin{array}{cc} A_{11} & A_{12} \\ A_{21} & A_{22} \end{array} \right),\qquad B= \left( \begin{array}{cc} B_{11} & B_{12} \\ B_{21} & B_{22} \end{array} \right),\qquad A \cdot B = \left( \begin{array}{cc} C_{11} & C_{12} \\ C_{21} & C_{22} \end{array} \right),$ wobei A_i,j, B_i,j, C_i,j Matrizen der Ordnung m2^k sind, und berechnet die Hilfsmatrizen der Ordnung m2^k

P₁ := (A₁₁ + A₂₂) * (B₁₁ + B₂₂)
P₂ := (A₂₁ + A₂₂) * B₁₁
P₃ := A₁₁ * (B₁₂ - B₂₂)
P₄ := A₂₂ * (B₂₁ + B₁₁)
P₅ := (A₁₁ + A₁₂) * B₂₂
P₆ := (A₂₁ - A₁₁) * (B₁₁ + B₁₂)
P₇ := (A₁₂ - A₂₂) * (B₂₁ + B₂₂)
C₁₁ = P₁ + P₄ - P₅ + P₇
C₁₂ = P₃ + P₅
C₂₁ = P₂ + P₄
C₂₂ = P₁ + P₃ - P₂ + P₆

indem man für die Multiplikation den Algorithmus A_m,k und für die Addition und Subtraktion den gewöhnlichen (elementweisen) Algorithmus verwendet.

Die Matrizen P₁, P₂, ..., P₇ können alle gleichzeitig berechnet werden. Dies gilt auch für die Matrizen C₁₁, ..., C₂₂, obwohl deren Berechnungsaufwand verglichen mit jenem für die Hilfsmatrizenn P₁, P₂, ..., P₇ verhältnismäßig klein ist, sodaß sich die parallele Berechnung oft nicht lohnt. Der Strassen-Algorithmus ist auf jeden Fall für eine Verwendung auf Parallelrechnern gut geeignet.

Hier ist eine Implementierung des Strassen-Algorithmus in C. Sie ist weder effizient, noch hübsch, noch gibt es eine Garantie, daß sie fehlerfrei ist. Ausserdem gibt sie allokierten Speicher nicht wieder frei. Dennoch sollte sie demonstrieren, wie und daß der Algorithmus funktioniert.

Komplexität des Strassen-Algorithmus

Der Strassen-Algorithmus ermöglicht die Berechnung des Produktes zweier Matrizen der Ordnung n=2^k mit 7^k Multiplikationen und weniger als 6.7^k Additionen und Subtraktionen, genauer:

K_mult(n) = n^log₂7 Multiplikationen und
K_add(n) = 6(n^log₂7 - n^log₂4) Additionen/Subtraktionen

Dieser Algorithmus hat also sowohl bezüglich der Additionen als auch bezüglich der Multiplikationen eine asymptotische Komplexität O(n^log₂7), die deutlich niefriger ist als jene des Standardalgorithmus. Für Matrizen mit allgemeiner Ordnung (nicht notwendigerweise n=2^k) gilt:

Satz 5.5.1: Das Produkt zweier quadratischer Matrizen der Ordnung n kann mit dem Strassen-Algorithmus mit weniger als 28.n^log₂7 arithmetischen Operationen berechnet werden.

Software für den Strassen-Algorithmus

Aus dem Grundkonzept des Strassen-Algorithmus effiziente Programme zu entwickeln, ist keine einfache Aufgabe. Der Strassen-Algorithmus galt daher auch lange nur als threoretisch interessantes Beispiel zur Komplexitätsreduktion bei der Matrizenmultiplikation. Von C. C. Douglas, M. Heroux, G. Slishman und R. M. Smith gibt es jedoch seit kurzem sehr effiziente Implementierungen für Einprozessor-Computer und Parallelrechner. Auch in die Softwarebibliotheken der Computerhersteller wurden bereits Implementierungen des Strassen-Algorithmus aufgenommen (z.B. sgemms und dgemms in der ESSL-Bibliothek).

Die "Grenzdimension" n_min, ab der eine Strassen-Implementierung weniger Rechenzeit erfordert als das entsprechende BLAS-3-Programm sgemm bzw. dgemm, liegt bei den meisten Computern zwischen 32 und 256. Bei größeren Matrizen tritt eine signifikante Verringerung der erforderlichen Gleitpunktoperationen und eine entsprechende Verkürzung der Rechenzeit ein.