EIN NEUER REKORD BEIM MULTIPLIZIEREN VON ZAHLENGITTERN
Zwei Matrizen – Zahlengitter – miteinander zu multiplizieren, ist eine der grundlegendsten Operationen der Informatik. Mit der Schulmethode wächst der Aufwand für die Multiplikation zweier n-mal-n-Gitter wie n³. Volker Strassens Algorithmus von 1969 war der erste, der es besser konnte – „subkubisch“, wie die Arbeit es nennt –, und seitdem messen Mathematiker den Fortschritt mit einer einzigen Zahl: dem Exponenten ω (Omega), der kleinsten Potenz von n, die bei wachsenden Gittern genügt.
Strassen drückte ihn unter 2,81. Jahrzehnte an Arbeit, in der Studie aufgelistet, haben ihn mit immer kleineren Schritten bis auf etwa 2,37 gesenkt. 2026 erreichten Emilien Dupont und Kollegen 2,371177. Reza Zadeh von der Firma Matroid, Inc. beweist nun ω < 2,37115924.
Ausgewählte Verbesserungen der oberen Schranke für ω, von Strassen 1969 bis zu dieser Arbeit. — Tabelle 1, Zadeh (2026), arXiv:2610.10593, CC BY 4.0.
Ein Rezept mit 212.820 Einstellungen
Diese Rekorde stammen nicht von einem cleveren Trick für kleine Gitter. Sie stammen von einem algebraischen Objekt namens Coppersmith-Winograd-Tensor, das sich rekursiv zerlegen und zu vielen unabhängigen Matrixprodukten neu zusammensetzen lässt. Wie es zerlegt wird, bestimmt eine riesige Menge an Entscheidungen: Wahrscheinlichkeitsverteilungen, Entropiestrafen und Matrixgrößen, festgelegt Ebene für Ebene. Jede gültige Wahl ergibt eine gültige Schranke; die Kunst besteht darin, eine gute zu finden.
Aufbauend auf dem Rahmenwerk von Josh Alman und Kollegen sowie auf der Formulierung von Dupont und Kollegen stimmte Zadeh 212.820 Zahlen gleichzeitig ab, mit drei Verfeinerungen:
- Neuskalierung nach Bedeutung. Manche Bausteine der Konstruktion tauchen nur selten auf, sodass ihr Einfluss auf das Ergebnis winzig ist und ein Optimierer sie kaum bewegt. Jede Zahl wurde danach neu skaliert, wie viel Gewicht ihr Baustein trägt.
- Sechs Regler für die Engpässe. Der endgültige Exponent wird von der schwächsten von drei konkurrierenden Größen in drei Stufen bestimmt. Eine eigene Korrektur nutzte nur sechs Stellgrößen, um sie im Gleichgewicht zu halten.
- Exakter Export. Das endgültige Rezept wurde in exakte Brüche mit Nennern von 2⁹⁶ umgewandelt.
Beweis durch Nachprüfen
Die Schranke ist ein computergestützter Beweis. Ein kurzes Programm, das nur die Standardbibliothek von Python nutzt – kein Netzwerk, kein Modell, kein Zusatzpaket –, rekonstruiert jede Verteilung aus den exakten Brüchen und wertet das Ergebnis mit garantierter Rundung aus. Es stellt fest, dass die entscheidende Größe positiv ist, um etwa 8,5 Milliardstel, was die Schranke beweist. Der Autor betont, was das nicht abdeckt: Das Programm ist prüfbarer Code, keine Formalisierung der gesamten Theorie in einem Beweisassistenten, und die Suche war lokal, ohne den Anspruch, dass das Rezept das bestmögliche ist.
Der Autor schreibt außerdem, dass generative KI-Werkzeuge, die nicht genannt werden, bei der numerischen Erkundung, der Software und dem Manuskript geholfen haben und dass frühe Codeteile auf Rechennotizen beruhten, die Eric Naslund öffentlich geteilt hatte. Ein separates öffentliches Computerzertifikat, veröffentlicht am 5. Oktober 2026, hatte 2,371169353 erreicht; der neue Wert liegt noch darunter.
Schneller, in der Theorie
Der Gewinn gegenüber Dupont und Kollegen beträgt 0,00001776 im Exponenten. Wie bei allen auf diese Weise gewonnenen Schranken ist die Garantie asymptotisch: Der Exponent allein verrät nicht, ab welcher Matrixgröße der neue Algorithmus die bestehenden tatsächlich schlagen würde. Was er ändert, ist die beste bekannte Antwort auf eine Frage, die seit 1969 im Raum steht – wie schnell lassen sich Zahlengitter im Prinzip multiplizieren?