Ich habe mich kürzlich aus komplett unmathematischen Gründen mit Galaxien beschäftigt. Und bin dabei auf eine sehr überraschende Zahl gestoßen:

ω < 2,3728639

Diese simple Formel hat mit »galaktischen Algorithmen« zu tun. Die gewaltigen Systeme aus hunderten Milliarden von Sternen tauchen dabei aber nicht auf. Beziehungsweise schon, aber auf eine eher unerwartete Weise. Die Zahl 2,3728639 trifft man im Zusammenhang mit dem »Coppersmith-Winograd-Algorithmus«, der sich mit der Multiplikation von Matrizen beschäftigt. Diese Zahlentabellen kann man rechnerisch genauso manipulieren wie man es auch mit einzelnen Zahlen tun kann, auch wenn man hier auf einige Besonderheiten beachten muss.

Beim klassischen mathematischen Weg der Matrixmultiplikation multipliziert man zuerst die erste Zahl in der ersten Zeile der ersten Matrix mit der ersten Zahl in der ersten Spalte der zweiten Matrix. Dazu addiert man das Produkt der zweiten Zahl der ersten Zeile der ersten Matrix mit der zweiten Zahl der ersten Spalte der zweiten Matrix. Und so weiter. Am Ende erhält man den ersten Eintrag für die erste Zeile der resultierenden Matrix. Den zweiten Eintrag der Ergebnismatrize bildet man analog aus der ersten Zeile der ersten Matrix mit der zweiten Spalte. So arbeitet man sich durch alle Zahlentabellen, und rein technisch ist die Aufgabe nicht schwer zu lösen. Aber es kann dauern, bis man fertig ist.

Will man zwei Matrizen mit je n · n Einträgen multiplizieren, steigt der Rechenaufwand dafür mit der dritten Potenz von n an. Das ist kein Problem, wenn man so eine Multiplikation nur einmalig durchführen muss. Aber die Multiplikation von Matrizen steckt überall in der modernen Technik; zum Beispiel in der Erstellung von Computergrafiken oder der Steuerung von Robotern. In der Wissenschaft kommen unter anderem Elektrotechnik und Quantenmechanik nicht ohne entsprechende Rechnungen aus.

Kleine Verbesserungen – großer Effekt

Und daher ist es eine durchaus wichtige Aufgabe, nach Methoden zu suchen, mit denen sich Matrizen schneller multiplizieren zu lassen. Die Mathematiker und Informatiker Don Coppersmith und Shmuel Winograd entwickelten 1990 genau so eine Methode, bei der der Rechenaufwand der Multiplikation nicht mit n³ anstieg, sondern mit n^2,375477. Das sieht nach einer eher unscheinbaren Verbesserung aus, könnte aber durchaus einen großen Unterschied machen, wenn sehr umfangreiche Matrizen sehr oft miteinander multipliziert werden müssen. 2014 konnte der französische Mathematiker François Le Gall den Exponenten ein weiteres Mal reduzieren: Von 2,375477 auf die in der oben genannten Formel 2,3728639.

Der von Le Gall verbesserte Coppersmith-Winograd-Algorithmus ist allerdings ein galaktischer Algorithmus. Diese Bezeichnung stammt von den Mathematikern Richard Lipton und Ken Regan und steht für ein Verfahren, das zwar theoretisch das Beste ist – das man aber, wie Lipton selbst sagt, »niemals benutzt, um tatsächlich irgendwas zu berechnen«.

Denn auch wenn man – wie im Fall des Coppersmith-Winograd-Algorithmus – zeigen kann, dass die Methode prinzipiell schneller ist als die üblichen Verfahren, ist sie doch nur dann effizienter, wenn die Datenmengen wirklich groß werden. Sehr viel größer nämlich als alle halbwegs vernünftig denkbaren und in der Praxis auftauchenden Datensätze. Es macht keinen Sinn, einen »galaktischen Algorithmus« auf »irdische« Datenmengen anzuwenden: Sie werden immer zu klein sein, um die Stärken der mathematischen Methode voll zur Geltung zu bringen.

Sinnlos sind sie dennoch nicht. Denn sie erlauben neue Einblicke in das, was möglich ist und sein könnte. Sie können der Mathematik neue Richtungen eröffnen. Und selbst ein galaktischer Algorithmus kann irgendwann brauchbar werden. Sollten in Zukunft etwa Quantencomputer in großem Stil zum Einsatz kommen, werden die heute noch ineffizienten Methoden auf einmal sehr praktisch und wichtig werden.