Informatiker sind ein anspruchsvoller Haufen. Für sie reicht es nicht aus, die richtige Antwort auf ein Problem zu finden – das Ziel besteht fast immer darin, die Antwort so effizient wie möglich zu erhalten.

Nehmen Sie sich die Multiplikation von Matrizen oder Zahlenfeldern vor. Im Jahr 1812 entwickelte der französische Mathematiker Jacques Philippe Marie Binet die grundlegenden Regeln, die wir unseren Schülern noch heute beibringen. Es funktioniert einwandfrei, aber andere Mathematiker haben Wege gefunden, den Prozess zu vereinfachen und zu beschleunigen. Nun ist die Aufgabe von den Prozess beschleunigen Die Matrixmultiplikation liegt an der Schnittstelle von Mathematik und Informatik, wo Forscher den Prozess bis heute weiter verbessern – obwohl die Fortschritte in den letzten Jahrzehnten eher bescheiden ausfielen. Seit 1987 seien numerische Verbesserungen bei der Matrizenmultiplikation „gering und ... äußerst schwer zu erreichen“, sagte er François Le Gall, Informatiker an der Universität Nagoya.

Jetzt haben drei Forscher – Ran Duan und Renfei Zhou von der Tsinghua-Universität und Hongxun Wu von der University of California, Berkeley – einen großen Schritt nach vorne gemacht, um dieses immerwährende Problem anzugehen. Ihre neue Ergebnisse, die letzten November auf der Konferenz „Foundations of Computer Science“ vorgestellt wurden, basieren auf einer unerwarteten neuen Technik, sagte Le Gall. Obwohl die Verbesserung selbst relativ gering war, bezeichnete Le Gall sie als „konzeptionell größer als andere frühere“.

Die Technik offenbart eine bisher unbekannte und damit ungenutzte Quelle potenzieller Verbesserungen und hat bereits Früchte getragen: Ein zweiter AufsatzDas im Januar veröffentlichte Buch baut auf dem ersten auf und zeigt, wie die Matrixmultiplikation noch weiter gesteigert werden kann.

„Das ist ein großer technischer Durchbruch“, sagte er William Kuszmaul, ein theoretischer Informatiker an der Harvard University. „Es ist die größte Verbesserung in der Matrixmultiplikation, die wir seit mehr als einem Jahrzehnt gesehen haben.“

Enter the Matrix

Es mag wie ein obskures Problem erscheinen, aber die Matrixmultiplikation ist eine grundlegende Rechenoperation. Es ist in einen großen Teil der Algorithmen integriert, die Menschen täglich für eine Vielzahl von Aufgaben verwenden, von der Darstellung schärferer Computergrafiken bis hin zur Lösung logistischer Probleme in der Netzwerktheorie. Und wie in anderen Bereichen der Berechnung ist Geschwindigkeit von größter Bedeutung. Selbst geringfügige Verbesserungen könnten letztendlich zu erheblichen Einsparungen an Zeit, Rechenleistung und Geld führen. Doch vorerst geht es den Theoretikern vor allem darum, herauszufinden, wie schnell der Prozess überhaupt sein kann.

Die traditionelle Art, zwei zu multiplizieren n-By-n Matrizen – durch Multiplikation der Zahlen aus jeder Zeile der ersten Matrix mit den Zahlen in den Spalten der zweiten – erfordern n³ separate Multiplikationen. Für 2x2-Matrizen bedeutet das 2³ oder 8 Multiplikationen.

Im Jahr 1969 stellte der Mathematiker Volker Strassen ein komplizierteres Verfahren vor, mit dem 2-mal-2-Matrizen in nur sieben Multiplikationsschritten und 18 Additionen multipliziert werden konnten. Zwei Jahre später wies der Informatiker Shmuel Winograd nach, dass sieben tatsächlich das absolute Minimum für 2x2-Matrizen sind.

Strassen nutzte dieselbe Idee, um zu zeigen, dass alles größer ist n-By-n Matrizen können auch mit weniger als multipliziert werden n³ Schritte. Ein Schlüsselelement dieser Strategie ist ein Verfahren namens Zerlegung – das Zerlegen einer großen Matrix in immer kleinere Untermatrizen, die am Ende nur 2 mal 2 oder sogar 1 mal 1 klein sein können (das sind nur einzelne Zahlen).

Der Grund für die Aufteilung eines riesigen Arrays in winzige Stücke ist demnach ziemlich einfach Virginia Vassilevska Williams, Informatiker am Massachusetts Institute of Technology und Co-Autor einer der neuen Arbeiten. „Für einen Menschen ist es schwierig, eine große Matrix (z. B. in der Größenordnung von 100 x 100) zu betrachten und sich den bestmöglichen Algorithmus auszudenken“, sagte Vassilevska Williams. Selbst 3x3-Matrizen sind noch nicht vollständig gelöst. „Trotzdem kann man einen schnellen Algorithmus, den man bereits für kleine Matrizen entwickelt hat, nutzen, um auch einen schnellen Algorithmus für größere Matrizen zu erhalten.“

Forscher haben herausgefunden, dass der Schlüssel zur Geschwindigkeit darin besteht, die Anzahl der Multiplikationsschritte zu reduzieren und so den Exponenten zu senken n³ (für die Standardmethode) so viel wie möglich. Der niedrigstmögliche Wert, n²ist im Grunde so lang, wie es dauert, nur die Antwort zu schreiben. Informatiker bezeichnen diesen Exponenten als Omega, ω, mit n^ω Dabei handelt es sich um die möglichst wenigen Schritte, die zur erfolgreichen Multiplikation von zwei erforderlich sind n-By-n Matrizen als n wird sehr groß. „Der Sinn dieser Arbeit“, sagte Zhou, der auch Mitautor des Papiers vom Januar 2024 war, „besteht darin, herauszufinden, wie nahe man an 2 herankommen kann und ob dies theoretisch erreicht werden kann.“

Ein Laserfokus

Im Jahr 1986 gelang Strassen ein weiterer großer Durchbruch, als er eingeführt was man die Lasermethode zur Matrixmultiplikation nennt. Strassen ermittelte damit einen oberen Omega-Wert von 2.48. Während die Methode nur einen Schritt bei Multiplikationen großer Matrizen darstellt, ist sie einer der wichtigsten, da die Forscher sie ständig verbessert haben.

Ein Jahr später stellten Winograd und Don Coppersmith einen neuen Algorithmus vor, der die Lasermethode wunderbar ergänzte. Diese Kombination von Werkzeugen wurde in praktisch allen nachfolgenden Bemühungen zur Beschleunigung der Matrixmultiplikation eingesetzt.

Hier ist eine vereinfachte Denkweise, wie diese verschiedenen Elemente zusammenpassen. Beginnen wir mit zwei großen Matrizen, A und B, die Sie miteinander multiplizieren möchten. Zuerst zerlegen Sie sie in viele kleinere Untermatrizen oder Blöcke, wie sie manchmal genannt werden. Als nächstes können Sie den Algorithmus von Coppersmith und Winograd als eine Art Bedienungsanleitung für die Handhabung und letztendlich den Zusammenbau der Blöcke verwenden. „Es sagt mir, was ich multiplizieren und was hinzufügen soll und welche Einträge wohin gehen“ in der Produktmatrix C, sagte Vassilevska Williams. „Es ist nur ein Rezept, um C aus A und B aufzubauen.“

Allerdings gibt es einen Haken: Manchmal erhält man Blöcke, die gemeinsame Einträge haben. Diese im Produkt zu belassen, käme einer doppelten Zählung dieser Einträge gleich, sodass Sie irgendwann diese doppelten Begriffe, sogenannte Überschneidungen, entfernen müssen. Forscher tun dies, indem sie die Blöcke, in denen sie sich befinden, „töten“ und ihre Komponenten auf Null setzen, um sie aus der Berechnung zu entfernen.

Hier kommt endlich die Lasermethode von Strassen ins Spiel. „Die Lasermethode funktioniert normalerweise sehr gut und findet im Allgemeinen eine gute Möglichkeit, eine Teilmenge von Blöcken zu zerstören, um die Überlappung zu beseitigen“, sagte Le Gall. Nachdem der Laser alle Überlappungen beseitigt oder „weggebrannt“ hat, können Sie die endgültige Produktmatrix C erstellen.

Die Kombination dieser verschiedenen Techniken führt zu einem Algorithmus zur Multiplikation zweier Matrizen mit einer insgesamt bewusst geringen Anzahl von Multiplikationen – zumindest in der Theorie. Die Lasermethode soll nicht praktikabel sein; Es ist nur eine Möglichkeit, darüber nachzudenken, wie man Matrizen idealerweise multipliziert. „Wir führen die Methode nie [auf einem Computer] aus“, sagte Zhou. „Wir analysieren es.“

Und diese Analyse führte zur größten Verbesserung von Omega seit mehr als einem Jahrzehnt.

Ein Verlust wird festgestellt

Der Artikel von Duan, Zhou und Wu vom letzten Sommer zeigte, dass Strassens Prozess noch deutlich beschleunigt werden könnte. Dies alles war auf ein Konzept zurückzuführen, das sie einen versteckten Verlust nannten und der tief in früheren Analysen vergraben war – „ein Ergebnis der unbeabsichtigten Zerstörung zu vieler Blöcke“, sagte Zhou.

Bei der Lasermethode werden Blöcke mit Überlappungen als zur Entsorgung vorgesehener Müll gekennzeichnet. Andere Blöcke gelten als wertvoll und werden gespeichert. Der Auswahlprozess ist jedoch etwas randomisiert. Ein als Müll eingestufter Block kann sich tatsächlich doch als nützlich erweisen. Dies war keine völlige Überraschung, aber durch die Untersuchung vieler dieser zufälligen Entscheidungen stellte Duans Team fest, dass die Lasermethode Blöcke systematisch unterschätzte: Es sollten mehr Blöcke gespeichert und weniger verworfen werden. Und wie so oft führt weniger Abfall zu mehr Effizienz.

„Die Möglichkeit, mehr Blöcke ohne Überlappung beizubehalten, führt somit zu … einem schnelleren Matrixmultiplikationsalgorithmus“, sagte Le Gall.

Nachdem Duans Team die Existenz dieses Verlusts nachgewiesen hatte, änderte es die Art und Weise, wie Blöcke mit der Lasermethode beschriftet wurden, und reduzierte so den Abfall erheblich. Infolgedessen legten sie eine neue Obergrenze für Omega bei etwa 2.371866 fest – eine Verbesserung gegenüber der vorherigen Obergrenze von 2.3728596. eingestellt im Jahr 2020 von Josh Alman und Vassilevska Williams. Das scheint eine bescheidene Änderung zu sein, da die Grenze nur um etwa 0.001 gesenkt wird. Aber es ist die größte Verbesserung, die Wissenschaftler seit 2010 gesehen haben. Das Ergebnis von Vassilevska Williams und Alman für 2020 verbesserte sich im Vergleich zum Vorgänger nur um 0.00001.

Aber was die Forscher am meisten begeistert, ist nicht nur der neue Rekord selbst – der nicht lange anhielt. Es ist auch die Tatsache, dass das Papier einen neuen Weg zur Verbesserung aufzeigte, der bis dahin völlig unbeachtet geblieben war. Seit fast vier Jahrzehnten verlassen sich alle auf die gleiche Lasermethode, sagte Le Gall. „Dann haben sie herausgefunden, dass wir es besser machen können.“

Das Papier vom Januar 2024 verfeinerte diesen neuen Ansatz und ermöglichte es Vassilevska Williams, Zhou und ihren Co-Autoren, den versteckten Verlust weiter zu reduzieren. Dies führte zu einer weiteren Verbesserung der Obergrenze von Omega und reduzierte sie auf 2.371552. Die Autoren verallgemeinerten diese Technik auch, um den Multiplikationsprozess für rechteckige (n-By-m) Matrizen – ein Verfahren, das in der Graphentheorie, im maschinellen Lernen und in anderen Bereichen Anwendung findet.

Weitere Fortschritte in dieser Richtung sind so gut wie sicher, aber es gibt Grenzen. Im Jahr 2015 gründeten Le Gall und zwei Mitarbeiter erwies sich dass der aktuelle Ansatz – die Lasermethode in Verbindung mit dem Coppersmith-Winograd-Rezept – kein Omega unter 2.3078 liefern kann. Um weitere Verbesserungen vorzunehmen, sagte Le Gall, „muss man den ursprünglichen [Ansatz] von Coppersmith und Winograd verbessern, der sich seit 1987 nicht wirklich geändert hat.“" Aber bisher hat niemand einen besseren Weg gefunden. Möglicherweise gibt es nicht einmal einen.

„Die Verbesserung von Omega ist tatsächlich Teil des Verständnisses dieses Problems“, sagte Zhou. „Wenn wir das Problem gut verstehen, können wir bessere Algorithmen dafür entwickeln. [Und] die Menschen befinden sich noch in einem sehr frühen Stadium des Verständnisses dieses uralten Problems.“