Besserer Algorithmus: Geschwindigkeitsgrenze bei Matrixmultiplikation geknackt

Dank besserer Analyse haben Forscher den Weg zu schnelleren Algorithmen geebnet. Die können etwa KI beschleunigen.

Artikel veröffentlicht am 11. März 2024, 12:45 Uhr, Johannes Hiltscher

Matrixmultiplikation ist Bestandteil vieler Algorithmen. (Bild: Marco Verch, Flickr/CC-BY 2.0)

Matrizen sind eine der am häufigsten verwendeten mathematischen Strukturen – sie ermöglichen nicht nur 3D-Grafiken, sondern werden auch etwa zur Abbildung von Optimierungsproblemen (g+) und neuronaler Netze verwendet. Die Matrixmultiplikation ist daher ein zentrales Element vieler Programme. Ihre große Bedeutung zeigt High Performance Linpack, der bekannteste Benchmark für Supercomputer: Er multipliziert zwei große Matrizen. Mathematiker versuchen seit Jahrzehnten, diesen wichtigen Algorithmus zu beschleunigen.

Zuletzt waren die erreichten Verbesserungen klein. Drei Forscher konnten die sogenannte obere Schranke, also den schlechtesten zu erwartenden Wert, für die Anzahl einzelner Multiplikationen bei der Matrixmultiplikation möglicherweise deutlich verbessern (via Quanta Magazine). Möglich macht das eine neue Herangehensweise, wie Ran Duan, Hongxun Wu und Renfei Zhou in einem im November 2023 beim Annual Symposium on Foundations in Computer Science vorgestellten Artikel beschreiben (Preprint bei Arxiv).

Die besten bisher bekannten Algorithmen bauten alle auf zwei Komponenten auf: Die erste ist der Coppersmith-Winograd-Algorithmus. Der zerlegt die Multiplikation zweier großer Matrizen in viele kleine Matrixmultiplikationen, anstatt, wie in der Schule gelernt, für jeden Ergebniswert zwei Vektoren zu multiplizieren. Es handelt sich um einen rekursiven Divide-and-Conquer-Algorithmus, der entfernt an die Schnelle Fourier-Transformation (g+) erinnert. Die Idee: Hierdurch lassen sich aufwendige Multiplikationen einsparen oder durch einfachere Additionen ersetzen.

Der verbesserte Laser

Der zweite Grundalgorithmus ist die von Volker Strassen entwickelte Laser-Methode: Sie wird benutzt, um die Ergebnisse der kleinen Matrixmultiplikationen zum Gesamtergebnis zusammenzufügen. Bei der Zerlegung können sich die kleinen Matrizen überlappen. Diese Stellen müssen gefunden und korrigiert werden. Die Laser-Methode identifiziert die problematischen Stellen – ist dabei aber ungenau.

Und genau an dieser Stelle haben Duan, Wu und Zhou angesetzt: Sie sahen sich die Struktur der Zerlegung – als Coppersmith-Winograd-Tensor bezeichnet – genauer an. Dabei entdeckten sie, dass die Laser-Methode zu viele mögliche Überlappungen aussortiert. Die Forscher entwickelten einen verbesserten Algorithmus, der in der Folge weniger Korrekturen erfordert. Ihre erste Komplexitätsabschätzung: n^2,371866 Multiplikationen für die Multiplikation zweier quadratischer Matrizen mit n x n Elementen. Gegenüber dem zuvor besten Algorithmus, der eine optimierte Laser-Methode verwendete, ist das zwar mit einer Verbesserung um etwa 0,001 nur unmerklich weniger Aufwand. Die neue Methode hat aber noch deutlich Potenzial.

Matrixmultiplikation mit quadratischem Aufwand?

Denn für die klassische Kombination aus Coppersmith-Winograd-Algorithmus und Laser-Methode gab es eine Abschätzung für eine untere Schranke: Der beste, damit denkbare Algorithmus könnte n^2,3725 Multiplikationen erfordern. Die haben Duan, Wu und Zhou unterboten. Aber auch für ihren Algorithmus gibt es eine untere Schranke: Besser als n^2,3078 wird es auch damit nicht. Dass es besser geht, zeigt eine Veröffentlichung beim Symposium of Discrete Algorithms (PDF): Hier wurde der erste Wert mit n^2,371552 bereits leicht unterboten. Hier wird zudem gezeigt, dass der ursprüngliche Algorithmus für quadratische n-x-n-Matrizen auf rechteckige n-x-m-Matrizen übertragbar ist – sie dominieren die praktischen Anwendungen.

Dennoch, so schreiben die Forscher, gebe es Hoffnung, dass einst die absolute Grenze erreicht werden könnte: n². Schneller kann die Multiplikation zweier Matrizen mit n x n Elementen nicht werden – damit wäre nur noch eine einzige Multiplikation pro Ergebniswert erforderlich.