Schnelle Matrix-Matrix-Multiplikationsalgorithmen: Ab wann lohnen die sich?
-
Hi.
Wenn man naiv eine Matrix-Matrix-Multiplikation programmiert, dann kriegt man einen Algorithmus, der bei (n x n) Matrizen mit n^3 skaliert. Es gibt aber auch Algorithmen, wie zum Beispiel den Coppersmith-Winograd Algorithmus, die deutlich besser skalieren. Mir ist aber nicht bewusst, dass die in der Praxis weit verbreitet sind und ich gehe irgendwie davon aus, dass die sich erst ab sehr grossen Matrixgroessen lohnen. Weiss jemand, ab was fuer Matrixgroessen die relevant werden? Oder gibt es einen anderen Grund, warum die nicht weit verbreitet sind?
-
Hi.
https://mathoverflow.net/questions/101531/how-fast-can-we-really-multiply-matrices schon gesehen?
-
Jodocus schrieb:
Hi.
https://mathoverflow.net/questions/101531/how-fast-can-we-really-multiply-matrices schon gesehen?Ne, das hatte ich noch nicht gesehen. Danke für den Link. Ich finde auf den ersten Blick dieses eine Paper, das da zum "CAPS" Algorithmus verlinkt wird ganz interessant. Nach Abstract sehen die da für diese Variante des Strassen Algorithmus deutliche Vorteile für eine Matrix mit einer Größe von ~90.000. Das ist jetzt nicht unendlich groß.
Generell scheint in dem von Dir verlinkten Thread aber gesagt zu werden, dass es eher keine Implementierungen gibt. Das finde ich absurd. Matrixgrößen von einigen 10.000 sind für viele Probleme von praktischer Relevanz.
-
Bei Problemgrößen in der Größenordnung n >> 1e4 (z.B. diskrete PDE-Löser) hat man es sehr oft mit dünnbesetzten Matrizen zu tun. Von daher würde man dort eher der Reihe nach die Matrizen draufmultiplizieren bzw. ab n >> 1e8 oder so die Algorithmen sogar zusätzlich matrixfrei implementieren. Man kann dort durchaus auf heutigen Supercomputern bis >1e13 Unbekannte gehen und auf Consumer-Maschinen immerhin noch bis O(1e10). Matrizen multiplizieren macht man in den Größenordnungen ähnlich gerne wie invertieren, also praktisch gar nicht. Mir sind keine Anwendungen bekannt wo man wirklich mit dichtbesetzten Systemen zu tun hat und es gleichzeitig irgendeinen Sinn macht die Matrizen miteinander zu multiplizieren. Schwebt Dir etwas bestimmtes vor? Ich denke in den meisten Fällen hilft eine clevere Algorithmik dabei das zu vermeiden, daher sind die asymptotisch besser skalierenden Algorithmen wahrscheinlich von geringer Relevanz, mal abgesehen davon, dass mir nicht bekannt wäre, dass sie gut parallelisieren kann.
-
@goi: Ich arbeite thematisch im Bereich der Dichtefunktionaltheorie. Wir haben es mit dicht besetzten Matrizen zu tun und unsere Problemgrößen wachsen mit der Zeit. Das Maximum sind momentan vermutlich Matrixgrößen von etwa 100.000x100.000. Praktisch regelmäßig haben wir es mit Matrixgrößen von 10.000x10.000 zu tun. Wir haben in unserem Programm zwei Codebereiche, die die Laufzeit bei solchen Problemgrößen dominieren. Beim einen Codebereich geht es im Wesentlichen um Matrixmultiplikationen, beim anderen Codebereich um die Diagonalisierung von Matrizen.
-
Tut mir Leid, ich kenne mich in dem Bereich nicht wirklich aus. Nur zum Verständnis: Was müsst ihr dann mit den zusammenmultiplizierten dichten Matrizen machen? Das wirkliche Multiplizieren lohnt sich ja erst dann, wenn ihr entweder an Speicherlimits stoßt, also nicht alle Faktoren speichern könnt, oder wirklich viele (O(n)) Operator-Anwendungen durchführen müsst. Wären hierarchische Matrizen ggf. eine Alternative? Dort kann man die elementaren Matrixoperationen mit annähernd linearem Aufwand (O(n log n)) durchführen, was sich darauf zurückführen lässt, dass man in diesem Format nicht wie bei der naiven Implementierung (oder cleveren Algorithmen wie Strassen und Co.) exakt rechnet, sondern gewisse Approximationen macht, die in vielen Anwendungen akzeptabel sein dürften, da die Matrizen oft sowieso Diskretisierungen der zugrundeliegenden Operatoren entsprechen. Leider lassen sich nicht alle Problemklassen mit hierarchischen Matrizen erschlagen, aber es lohnt sich vielleicht mal in die gesammelten Werke von Hackbusch, Grasedyck und Co. zu schauen.