Matrix Multiplication links

By Wolfgang Keller
Originally published 2025-06-15
Last modified 2025-06-15

Der klassische Algorithmus mit Laufzeit \(O(n^{\log_2 7}) \approx O(n^{2.807})\) ist die Strassen-Multiplikation.
Wenn wir bereit sind, in die Klasse galaktischer Algorithmen zu gehen:
- Lange Zeit war der Coppersmith-Winnograd-Algorithmus (1990) (mit Laufzeit ca. \(O(n^{2.3727})\) Rekordhalter.
- Ganz aktuell (2024) ist bekannt ([2404.16349v2] More Asymmetry Yields Faster Matrix Multiplication [published 2024-10-20T04:13:13Z; visited 2025-06-15T13:31:59Z]), dass man mit \(O(n^{2.371399})\) auskommt.
- Wikipedia (Computational complexity of matrix multiplication - Wikipedia [published 2025-03-18T21:57; visited 2025-06-15T13:10:08Z]) liefert allerhand weitere Zwischenresultate, die seit 2010 publiziert wurden.
- Unter If you are interested in how those tensor methods work, the authors have another... | Hacker News [published 2021-03-23T21:00:13; visited 2025-06-15T13:39:35Z] wird folgendes Übersichtspaper (2018) empfohlen: [1810.08671v1] Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication [published 2018-10-19T20:07:08Z; visited 2025-06-15T13:54:35Z] (Themen: Laser method (Strassen), Group theoretic approach (Cohn and Umans))