Ich frage mich, was ein guter, performanter Algorithmus für die Matrixmultiplikation von 4×4-Matrizen ist. Ich implementiere einige affine Transformationen und bin mir bewusst, dass es mehrere Algorithmen für eine effiziente Matrixmultiplikation gibt, wie Strassen. Aber gibt es einige Algorithmen, die für so kleine Matrizen besonders effizient sind? Die meisten Quellen, die ich mir angesehen habe, sind asymptotisch die effizientesten.
Kommentare
- Ich denke, dort ‚ kann eine gewisse Leistung erzielt werden, wenn festgestellt wird, dass affine Transformationen für 3D nur eine 4×3-Submatrix ändern, da die unterste Zeile immer
0 0 0 1ist. Daher können Sie das Multiplizieren mit dieser Zeile vermeiden. - Sie haben Recht, dies ist eine Optimierung, die ich bereits in der naiven o (n ^ 3) -Implementierung übernommen habe, die ich gerade verwende.
- Als ich das letzte Mal damit gespielt habe, war die schnellste Antwort die offensichtlichste. Ich habe den blindesten naiven Code geschrieben, der meine Bedeutung so effektiv erfasst hat, dass der Compiler das Tageslicht mithilfe von SSE optimiert hat. Es hat brillante Dinge getan, wie Matrizen in SSE-Registern zu halten, anstatt sie in den RAM zu lassen. Je mehr ich selbst versuchte, es zu optimieren, desto weniger war der Compiler bei der Konvertierung meiner Methoden in SIMD
Antwort
Wikipedia listet vier Algorithmen für die Matrixmultiplikation von zwei nxn-Matrizen auf.
Der klassische Algorithmus, den ein Programmierer schreiben würde, ist O (n 3 ) und wird als „Schoolbook Matrix Multiplication“ aufgeführt. Ja. O (n 3 ) ist ein kleiner Treffer. Schauen wir uns den nächstbesten an.
Der Strassen-Algorithmus ist O (n ). Dieser würde funktionieren – er hat einige Einschränkungen (z. B. die Größe ist eine Zweierpotenz) und eine Einschränkung in der Beschreibung:
Im Vergleich zur herkömmlichen Matrixmultiplikation fügt der Algorithmus eine beträchtliche O (n 2) -Arbeitslast zusätzlich / subtrahiert hinzu; Ab einer bestimmten Größe ist es daher besser, die konventionelle Multiplikation zu verwenden.
Für diejenigen, die sich für diesen Algorithmus und seine Ursprünge interessieren, ist Wie kam Strassen auf seine Matrixmultiplikationsmethode? kann eine gute Lektüre sein. Es gibt einen Hinweis auf die Komplexität dieser anfänglichen O (n 2) -Arbeitslast, die hinzugefügt wird, und warum dies teurer wäre als nur die klassische Multiplikation.
Also wirklich ist O (n + n 2.807 ), wobei dieses Bit über den unteren Exponenten n beim Schreiben von großem O ignoriert wird arbeiten an einer schönen 2048×2048 Matrix, dies könnte nützlich sein. Bei einer 4×4-Matrix wird sie wahrscheinlich langsamer, da sich der Overhead die ganze Zeit auffrisst.
Und dann gibt es die Coppersmith-Winograd Algorithmus , der O (n 2.373 ) mit einigen Verbesserungen ist. Er enthält auch eine Einschränkung:
Der Coppersmith-Winograd-Algorithmus wird häufig als Baustein in anderen Algorithmen verwendet, um theoretische Zeitgrenzen zu beweisen. Im Gegensatz zum Strassen-Algorithmus wird er jedoch in der Praxis nicht verwendet, da er nur für Matrizen einen Vorteil bietet, die so groß sind, dass sie dies nicht können von moderner Hardware verarbeitet werden.
Es ist also besser, wenn Sie an super großen Matrizen arbeiten, aber auch hier nicht nützlich für eine 4×4-Matrix.
Dies spiegelt sich auch auf der Wikipedia-Seite in wider. Matrixmultiplikation: Subkubische Algorithmen , die das Warum von Dingen erkennen, die schneller laufen:
Es gibt Algorithmen, die pr bessere Laufzeiten als die einfachen. Der erste, der entdeckt wurde, war Strassens Algorithmus, der 1969 von Volker Strassen entwickelt wurde und oft als „schnelle Matrixmultiplikation“ bezeichnet wird. Er basiert auf einer Methode zur Multiplikation von zwei 2 × 2-Matrizen, die nur 7 Multiplikationen erfordert (anstelle von die übliche 8) auf Kosten mehrerer zusätzlicher Additions- und Subtraktionsoperationen. Wenn diese rekursiv angewendet wird, ergibt sich ein Algorithmus mit multiplikativen Kosten von O (n log 2 2 7) div id = „592dd3fb3a“>
O (n ). Strassens Algorithmus ist komplexer und die numerische Stabilität ist im Vergleich zum naiven Algorithmus verringert, in Fällen jedoch schneller n> 100 oder so und erscheint in mehreren Bibliotheken, wie z. B. BLAS.
Und das bringt uns auf den Punkt, warum die Algorithmen schneller sind – Sie tauschen einen Kompromiss aus einige numerische Stabilität und einige zusätzliche Einstellungen. Dieses zusätzliche Setup für eine 4×4-Matrix ist viel mehr als die Kosten für die Multiplikation.
Und jetzt, um Ihre Frage zu beantworten:
Aber gibt es einige Algorithmen, die für so kleine Matrizen besonders effizient sind?
Nein, es gibt keine Algorithmen, die für die 4×4-Matrixmultiplikation optimiert sind, da O (n 3 ) recht vernünftig funktioniert bis Sie feststellen, dass Sie bereit sind, einen großen Treffer für Overhead zu erzielen. Für Ihre spezifische Situation kann es zu einem gewissen Aufwand kommen, dass Sie im Voraus bestimmte Dinge über Ihre Matrizen wissen (z. B. wie viele Daten wiederverwendet werden), aber am einfachsten ist es, guten Code für das O zu schreiben (n 3 ) Lösung, lassen Sie den Compiler damit umgehen und profilieren Sie sie später, um festzustellen, ob der Code tatsächlich der langsame Punkt in der Matrixmultiplikation ist.
Bezogen auf Math.SE: Minimale Anzahl von Multiplikationen, die zum Invertieren einer 4×4-Matrix erforderlich sind
Antwort
Oft sind einfache Algorithmen für sehr kleine Mengen am schnellsten, da komplexere Algorithmen normalerweise eine Transformation verwenden, die einen gewissen Overhead verursacht. Ich denke, Ihre beste Wahl ist nicht ein effizienterer Algorithmus (ich denke, die meisten Bibliotheken verwenden einfache Methoden), sondern eine effizientere Implementierung, zum Beispiel eine mit SIMD-Erweiterungen (unter der Annahme von x86- oder amd64-Code) oder handgeschrieben in Assembly . Auch das Speicherlayout sollte gut durchdacht sein. Sie sollten in der Lage sein, genügend Ressourcen dafür zu finden.
Antwort
Bei der 4×4-Matten / Matten-Multiplikation sind algorithmische Verbesserungen häufig nicht möglich . Der grundlegende Algorithmus für die Komplexität der kubischen Zeit schneidet in der Regel recht gut ab, und alles, was schicker ist, verschlechtert die Zeiten eher, als dass es die Zeiten verbessert. Nur im Allgemeinen sind ausgefallene Algorithmen ungeeignet, wenn kein Skalierbarkeitsfaktor beteiligt ist (z. B. der Versuch, ein Array schnell zu sortieren, das immer 6 Elemente enthält, im Gegensatz zu einer einfachen Einfügung oder Blasensortierung) Dinge wie die Matrixtransposition hier zur Verbesserung der Referenzlokalität unterstützen auch nicht die Referenzlokalität, wenn eine gesamte Matrix in eine oder zwei Cache-Zeilen passen kann. Bei dieser Art von Miniaturskala ergeben sich die Verbesserungen im Allgemeinen aus Optimierungen von Anweisungen und Speicher auf Mikroebene, z. B. der richtigen Ausrichtung der Cache-Zeilen.
Kommentare
- Tolle Antwort! Ich ‚ habe noch nie von dem SoA-Akronym gehört (zumindest auf Niederländisch ist es ein Akronym für ‚ seksueel overraagbare aandoening ‚ was ‚ sexuell übertragbare Krankheit ‚ bedeutet … aber das ‚ ist hoffentlich nicht das, was du hier meinst). Die Technik scheint klar zu sein, ich ‚ bin sogar ziemlich überrascht, dass es einen Namen dafür gibt. Wofür steht SoA?
- @Ruben Structure of Arrays im Gegensatz zu Arrays of Structures. SoAs können auch PITAs sein – am besten für Ihre kritischsten Pfade gespeichert. Hier ‚ ist ein netter kleiner Link, den ich zu diesem Thema gefunden habe: stackoverflow.com/questions/17924705/…
- Vielleicht möchten Sie C ++ 11 / C11
alignas.
Antwort
Wenn Sie sicher sind, dass Sie nur 4×4 multiplizieren müssen Matrizen, dann brauchen Sie sich überhaupt keine Gedanken über einen allgemeinen Algorithmus zu machen. Sie können einfach zwei Zeiger aufnehmen und diese verwenden:
(Ich würde dringend empfehlen, dies auf automatisierte Weise zu übersetzen.)
Der Compiler wäre dann Optimal positioniert, um diesen Code zu optimieren (um Teilsummen wiederzuverwenden, die Mathematik neu zu ordnen usw.), da er alles sehen kann, es keine dynamischen Schleifen und keinen Kontrollfluss gibt.
Kaum vorstellbar, dass dies ohne geschlagen werden kann Verwenden von Intrinsics.
Antwort
Sie können die asymptotische Komplexität nicht direkt vergleichen, wenn Sie n anders definieren. Sie sind es gewohnt, die Komplexität von Algorithmen in flachen Datenstrukturen wie Listen zu vergleichen, wobei n als Gesamtzahl der Elemente in definiert ist die Liste, aber die Matrixalgorithmen definieren n als nur die Länge einer Seite .
Durch diese Definition von n, etwas so Einfaches wie das einmalige Betrachten jedes Elements, um es zu drucken, was Sie normalerweise als O (n) betrachten würden, ist O (n 2 ) . Wenn Sie n als die Gesamtzahl der Elemente in der Matrix definieren, dh n = 16 für eine 4×4-Matrix, beträgt die naive Matrixmultiplikation nur O (n 1,5 ), was ziemlich gut ist.
Am besten nutzen Sie die Parallelität mithilfe von SIMD-Anweisungen oder einer GPU, anstatt zu versuchen, den Algorithmus zu verbessern, der auf der falschen Annahme basiert, dass O (n 3 ) ist so schlecht wie es wäre, wenn n vergleichbar mit einer flachen Datenstruktur definiert wäre.