Die theoretische Informatik feiert seit Jahrzehnten Fortschritte bei der algorithmischen Komplexität der Matrizenmultiplikation – doch in der Praxis sind diese Durchbrüche irrelevant. Die asymptotische Schranke wurde inzwischen auf O(n^2.37117) gedrückt, doch wie ein Informatiker auf Mastodon kürzlich kritisch anmerkte: Diese Algorithmen sind „utterly irrelevant" für reale Anwendungen.
Das grundlegende Problem ist simpel: Die Multiplikation zweier quadratischer Matrizen erfordert nach der Standardmethode O(n³) Operationen. Da die Matrizen selbst aber nur O(n²) Einträge enthalten, stellt sich die Frage, ob ein effizienterer Algorithmus möglich ist.
Seit 1969 ist bekannt, dass eine bessere asymptotische Komplexität als n³ erreichbar ist. Strassens Algorithmus liefert tatsächlich praktischen Nutzen – allerdings nur in einem sehr engen Anwendungsbereich: für die Multiplikation dichter Matrizen ab Dimension 500 und höher. Doch wie viele Informatiker jemals die Notwendigkeit hatten, solche Matrizen zu multiplizieren? Der Mastodon-Nutzer bringt es auf den Punkt: „Which I have never needed to do."
Seit dem Durchbruch haben Forscher die theoretische Komplexitätsschranke schrittweise weiter gesenkt. Die aktuelle Bestmarke liegt bei O(n^2.37117). Auf dem Papier ein beeindruckender Fortschritt – doch die Algorithmen hinter diesen Verbesserungen finden keine Verwendung außerhalb der Forschungsliteratur. Sie sind mathematische Konstrukte mit so großen Konstanten, dass sie erst bei Matrixgrößen relevant würden, die in keiner realen Anwendung vorkommen.
Die Kluft zwischen theoretischer Komplexitätsforschung und praktischer Algorithmik ist evident: Forschungsfinanzierung, wissenschaftliche Reputation und akademische Karrieren hängen an asymptotischen Verbesserungen – nicht an der Frage, ob ein Algorithmus jemals auf echter Hardware laufen wird.
