In einer kürzlich erschienenen Arbeit wurde ein neuer Geschwindigkeitsrekord für die Multiplikation zweier Matrizen aufgestellt . Es markiert auch das Ende einer Ära für die Methode, mit der Wissenschaftler seit Jahrzehnten forschen.
Mathematiker streben danach, ein mythisches Ziel zu erreichen - den zweiten Grad (Exponent zwei), dh ein Paar von n x n Matrizen in nur n 2 Schritten zu multiplizieren . Die Forscher nähern sich ihrem Ziel, aber werden sie es jemals erreichen können?
Für Informatiker und Mathematiker ist die Idee des "zweiten Grades" mit der Idee einer perfekten Welt verbunden.
"Es ist schwer, zwischen wissenschaftlichem Denken und unbegründetem Tagträumen zu unterscheiden", gibt Chris Umans vom California Institute of Technology zu. "Ich möchte, dass der Abschluss zwei ist, weil er schön ist."
Unter dem Gesichtspunkt der erforderlichen Anzahl von Schritten ist "zweiter Grad" die ideale AusführungsgeschwindigkeitEine der grundlegendsten mathematischen Operationen ist die Matrixmultiplikation. Wenn der zweite Grad erreichbar ist, kann die Matrixmultiplikation so schnell wie physikalisch möglich durchgeführt werden. Wenn dies nicht der Fall ist, stecken wir in einer Welt fest, die unseren Träumen nicht gerecht wird.
Matrizen sind Anordnungen von Zahlen. Wenn die beiden Matrizen übereinstimmen (die Anzahl der Spalten im ersten Faktor entspricht der Anzahl der Zeilen im zweiten), können sie multipliziert werden, um die dritte zu erhalten. Wenn Sie beispielsweise mit einem 2 x 2-Matrixpaar beginnen, ist das Produkt auch eine 2 x 2-Matrix mit vier Elementen. Allgemeiner ist das Produkt eines Paares von n x n Matrizen eine andere n x n Matrix mit n 2 Elementen.
Daher ist die kleinstmögliche Anzahl von Schritten zum Multiplizieren von Matrizenpaaren n 2 , dh die Anzahl von Schritten, die nur zum Schreiben der Antwort erforderlich sind. Daher der Name "zweiter Grad".
Und obwohl niemand genau weiß, ob dies erreicht werden kann, bewegen sich die Forscher weiter in diese Richtung.
Der im Oktober veröffentlichte Artikel kommt dem Ziel noch näher und beschreibt die bisher schnellste Methode zur Multiplikation zweier Matrizen. Das Ergebnis erhielten Josh Alman , Doktorand an der Harvard University, und Virginia Wasilewska Williamsvom Massachusetts Institute of Technology, verringert den Grad der vorherigen Bestleistung um etwa ein Hunderttausendstel. Dies ist wirklich eine großartige Leistung in diesem Bereich, die durch sorgfältige Arbeit erreicht wird.
Um diesen Prozess besser zu verstehen und zu verstehen, wie er verbessert werden kann, beginnen wir mit einem Paar von 2 x 2 Matrizen A und B. Bei der Berechnung jedes Elements ihres Produkts verwenden Sie die entsprechende Zeile aus A und die entsprechende Spalte aus B. Um das Element oben rechts zu erhalten, multiplizieren Sie die erste Zahl in der ersten Zeile A mit der ersten Zahl in der zweiten Spalte B, multiplizieren Sie dann die zweite Zahl in der ersten Zeile A mit der zweiten Zahl in der zweiten Spalte B und addieren Sie die beiden Produkte.
Samuel Velasco / Quanta Magazine
Diese Operation ist bekannt als Erhalten eines "Punktprodukts" einer Zeile mit einer Spalte (manchmal als "inneres Produkt" bezeichnet). Um andere Elemente im Matrixprodukt zu berechnen, wiederholen Sie den Vorgang mit den entsprechenden Zeilen und Spalten.
Im Allgemeinen besteht die klassische 2 × 2-Matrixmultiplikationsmethode aus acht Multiplikationen und mehreren Additionen. Typischerweise erfordert dieses Verfahren zum Multiplizieren von zwei n x n Matrizen n 3 Multiplikationen.
Mit zunehmender Größe der Matrizen wächst die Anzahl der Multiplikationen, die erforderlich sind, um ihr Produkt zu finden, viel schneller als die Anzahl der Additionen. Um das Produkt von 2 x 2 Matrizen zu finden, sind nur acht Zwischenmultiplikationen erforderlich, und um das Produkt von 4 x 4 Matrizen zu finden, sind bereits 64 davon vorhanden. Die Anzahl der Additionen, die erforderlich sind, um die Summe dieser Matrizen zu erhalten, beträgt jedoch nicht viel anders. Normalerweise entspricht die Anzahl der Additionen der Anzahl der Elemente in der Matrix, dh vier für 2 x 2-Matrizen und 16 für 4 x 4-Matrizen. Dieser Unterschied zwischen Addition und Multiplikation macht deutlich, warum Forscher die Geschwindigkeit der Matrixmultiplikation messen ausschließlich in Bezug auf die Anzahl der erforderlichen Multiplikationen.
„Multiplikationen sind alles“, sagt Umans. „Der Exponent hängt letztendlich ganz von der Anzahl der Multiplikationen ab. Ergänzungen verschwinden gewissermaßen. "
Über Jahrhunderte glaubten die Menschen, dass n 3 der schnellste Weg ist, Matrizen zu multiplizieren . Berichten zufolge wollte Volker Strassen 1969 beweisen, dass es unmöglich ist, 2 x 2 Matrizen mit weniger als acht Multiplikationen zu multiplizieren. Anscheinend konnte er immer noch keinen Beweis finden, und nach einer Weile verstand er warum: Tatsächlich gibt es eine Möglichkeit, dies mit sieben Multiplikationen zu tun!
Strassen entwickelte eine komplexe Reihe von Beziehungen, die es ihm ermöglichten, eine dieser acht Multiplikationen durch 14 zusätzliche Ergänzungen zu ersetzen. Der Unterschied mag wie ein subtiler Unterschied erscheinen, aber er zahlt sich aus, weil die Multiplikation mehr als die Addition beiträgt. Als Strassen einen Weg fand, eine Multiplikation für kleine 2 x 2-Matrizen loszuwerden, entdeckte er eine Möglichkeit, die er beim Multiplizieren größerer Matrizen nutzen konnte.
"Diese winzige Änderung führt zu enormen Verbesserungen beim Umgang mit großen Matrizen", sagt Williams.
Virginia Wasilewska Williams vom Massachusetts Institute of Technology und Josh Alman von der Harvard University entdeckten den schnellsten Weg, zwei Matrizen in n 2.3728596 Schritten zu multiplizieren . Jared Charney; Richard T.K. Falke
Angenommen, Sie möchten ein Paar von 8 x 8-Matrizen multiplizieren. Eine Möglichkeit, dies zu tun, besteht darin, jede große Matrix in vier 4 x 4-Matrizen aufzuteilen, sodass jede vier Elemente enthält. Da die Elemente einer Matrix auch Matrizen sein können, können Sie sich die ursprünglichen Matrizen als ein Paar von 2 x 2 Matrizen vorstellen, von denen jedes der vier Elemente selbst eine 4 x 4-Matrix ist x 4 Matrizen können in vier Matrizen der Größe 2 x 2 aufgeteilt werden.
Die Idee hinter dieser mehrfachen Aufteilung großer Matrizen in kleinere ist, dass Sie den Strassen-Algorithmus immer wieder auf kleinere Matrizen anwenden und seine Methode verwenden können, um die Anzahl der Schritte zu reduzieren bei jedem Schritt. Im Allgemeinen erhöhte der Strassen-Algorithmus die Geschwindigkeit der Matrixmultiplikation mit n 3 bis n 2,81 multiplikative Schritte.
Der nächste wichtige Schritt in der Entwicklung der Idee erfolgte Ende der 1970er Jahre, als ein grundlegend neuer Ansatz zur Lösung dieses Problems auftauchte. Es beinhaltet die Übersetzung der Matrixmultiplikation in ein anderes Problem der rechnergestützten linearen Algebra unter Verwendung von Objekten, die als Tensoren bezeichnet werden. Die in diesem Problem verwendeten Tensoren sind dreidimensionale Anordnungen von Zahlen, die aus vielen verschiedenen Teilen bestehen, von denen jeder wie ein kleines Matrixmultiplikationsproblem aussieht.
Die Matrixmultiplikation und dieses Tensorproblem sind in gewissem Sinne einander äquivalent, aber die Forscher hatten bereits schnellere Verfahren, um letzteres zu lösen. Sie standen daher vor der Aufgabe, den "Wechselkurs" zwischen ihnen zu bestimmen: Welche Größenmatrizen können mit denselben Rechenkosten multipliziert werden, die zur Lösung des Tensorproblems erforderlich sind?
"Dies ist ein in der theoretischen Informatik weit verbreitetes Konzept: Aufgaben zu transformieren und Analogien zwischen ihnen zu ziehen, um zu zeigen, dass sie gleichermaßen einfach oder komplex sind", sagte Alman.
1981 verwendete Arnold Schönhage diesen Ansatz, um zu beweisen, dass die Matrixmultiplikation in n 2.522 Schritten durchgeführt werden kann. Strassen nannte diesen Ansatz später die "Lasermethode" .
In den letzten Jahrzehnten ist jede Verbesserung der Matrixmultiplikation auf Verbesserungen der Lasermethode zurückzuführen, da Forscher effizientere Wege gefunden haben, um das Problem zu transformieren. In ihrem neuen Beweis verwischen Alman und Williams die Unterscheidung zwischen den beiden Problemen und zeigen, dass es möglich ist, die Anzahl der Multiplikationen zu reduzieren. "Insgesamt haben Josh und Virginia einen Weg gefunden, Machine Computing innerhalb der Lasermethode anzuwenden, und die bisher besten Ergebnisse erzielt", sagte Henry Cohn.von Microsoft Research.
In ihrem Artikel wird die theoretische Grenze für die Geschwindigkeit der Matrixmultiplikation auf n 2,3728596 verbessert .
Auch dank dieser Forschung kann Williams die Krone im Bereich der Matrixmultiplikation wiedererlangen, die sie zu Recht im Jahr 2012 erhielt (n 2,372873 ), und dann verloren im Jahr 2014 auf François Le Gall (n 2,3728639 ).
Trotz all dieser Rennen und Siege wird deutlich, dass bei diesem Ansatz das Gesetz der Verringerung der Rendite oder der Verringerung der Rendite gilt. Höchstwahrscheinlich hat die Verbesserung von Alman und Williams die Möglichkeiten der Lasermethode fast vollständig ausgeschöpft, aber das endgültige theoretische Ziel nicht erreicht.
"Es ist unwahrscheinlich, dass Sie mit dieser Methodenfamilie in die Nähe des zweiten Grades gelangen", sagte Umans.
Dies erfordert die Entdeckung neuer Methoden und die feste Überzeugung, dass dies überhaupt möglich ist.
Williams erinnert sich an eines seiner Gespräche mit Strassen darüber: „Ich fragte ihn, ob er es für möglich halte, den zweiten Grad für die Matrixmultiplikation zu erreichen, und er antwortete:„ Nein, nein, nein, niemals! “.