MATLAB-Matrixmultiplikation (der beste Berechnungsansatz)

10

Ich muss eine Koordinatentransformation zwischen zwei Referenzsystemen (Achsen) durchführen. Dafür müssen drei Matrizen ( ) multipliziert werden, da einige Zwischenachsen verwendet werden. Ich habe über zwei Lösungsansätze nachgedacht:3×3

Methode 1 : Die Multiplikation direkt durchführen,

vf=R1 R2 R3 vi

Methode 2 : In Schritte aufteilen:

  1. v3i=R3 vi
  2. v23=R2 v3i
  3. vf=R1 v23

wo:

R 2 R 3 3 × 3R1 , und sind MatrizenR2R33×3

v i v 3 i v 23 3 × 1vf , , , sind Vektorenviv3iv233×1

Ich würde gerne wissen, welche Methode rechnerisch effizienter ist (weniger Zeit), um die Transformation durchzuführen (dies wird häufig durchgeführt).

julianfperez
quelle
4
Verwenden Sie Quaternionen .
Chris Taylor
@ ChrisTaylor: Vielen Dank für Ihren Vorschlag.
Julianfperez
2
Bitte nicht überqueren.
Ripped Off
2
Beachten Sie, dass hier zwei Fragen und StackOverflow gekreuzt wurden. Die Fragen und ihre Kommentare und Antworten wurden in diese zusammengeführt.
Aron Ahmadia
@ Will und AronAhmadia: Es tut mir leid. Ich wusste nicht, dass das Crossposting verboten ist. Ich habe meine Fragen immer auf StackOverflow gepostet, aber heute habe ich diese neue Site gefunden und dachte, ich könnte vielleicht auch hier Hilfe finden.
Julianfperez

Antworten:

17

Matlab interpretiert Sequenzen von Multiplikationen und / oder Divisionen von links nach rechts. Daher ist viel teurer als , da Sie zwei Matrixprodukte und ein Matrix-Vecor-Produkt anstelle von drei Matrix-Vektor-Produkten haben.A ( B ( C v ) )ABCvA(B(Cv))

Andererseits sollte etwas schneller sein, als wenn Sie die Zwischenprodukte in separaten Vektoren speichern, wie Ihre zweite Methode vorschlägt.A(B(Cv))

Um allgemein herauszufinden, wie die Auswirkungen kleiner Programmierunterschiede auf große Berechnungen gemessen werden können, schreiben Sie an die Matlab-Eingabeaufforderung "Hilfsprofil".

Arnold Neumaier
quelle
Vielen Dank für die interessanten Informationen in Ihrer Antwort.
Julianfperez
Warum ist es schneller, wenn Sie die Zwischenprodukte speichern?
Federico Poloni
@FedericoPoloni: Ich hatte geschrieben, dass es etwas schneller ist , die Zwischenprodukte nicht zu speichern.
Arnold Neumaier
@ArnoldNeumaier Ooh sorry ich habe falsch gelesen. :)
Federico Poloni
14

Für den Anfang würde ich keine Zwischenvariablen verwenden, sondern Klammern. Es sei denn natürlich, Sie interessieren sich für die Zwischenergebnisse, aber ich vermute nicht.

Ich habe in Matlab Folgendes versucht:

>> N = 500;                                             
>> A = rand(N); B = rand(N); C = rand(N); v = rand(N,1);

>> tic, for k=1:100, A*B*C*v; end; toc
Elapsed time is 3.207299 seconds.

>> tic, for k=1:100, A*(B*(C*v)); end; toc
Elapsed time is 0.108095 seconds.

Ich muss jedoch sagen, dass dies ziemlich beängstigend ist. Ich bin immer davon ausgegangen, dass Matlab bei der Matrixmultiplikationsreihenfolge klug ist, da dies ein bekanntes Problem mit einfachen und effizienten Lösungen ist.

Pedro
quelle
Haben Sie den Teil verpasst, in dem die Matrizen 3x3 sind? :)
Aron Ahmadia
2
@AronAhmadia: Ups ... Ich habe das verpasst, danke. Ich denke, für diese Matrixgrößen ist das ganze Problem umstritten, aber ich bin immer noch überrascht über die Ergebnisse für große N.
Pedro
7
Ich vermute, MATLAB folgt den C-Prioritätsregeln für die Ausdrucksbewertung, da Gleitkomma-Mathematik nicht assoziativ ist und sie davon ausgehen müssen, dass Sie wissen, was Sie tun :)
Aron Ahmadia
2
@Pedro: Danke für deine Antwort. Für die Matrixdimension 3x3 habe ich überprüft, dass Ihre Lösung auch besser ist als die übliche (ohne Klammern) Matrixmultiplikation.
Julianfperez
+1 Danke, dass Sie eine einfache und einfache Methode zur Messung der Laufzeit gezeigt haben
Steven Magana-Zook
14

Da die Matrizen so klein sind, werden alle Kosten im Anrufaufwand anfallen. Wenn Sie die Transformation mehrmals durchführen, ist es schneller, sie D=A*B*Ceinmal vorab zu berechnen und dann für jeden Vektor anzuwenden v_f=D*v_i. Sie können dies auch in eine mex-Datei aufnehmen.

Aron Ahmadia
quelle
Vielen Dank für Ihre Antwort. In meinem Fall handelt es sich bei den Matrizen um Rotationsmatrizen (sie hängen von einem Winkelwert ab und dieser ändert sich), sodass das Produkt A B C nicht immer dasselbe ist.
Julianfperez