Boost und inverse Matrix

otze

Taurin schrieb:

Darf ich nochmal nachfragen, was du mit der Inversen machen möchtest? Weiter oben hat ja schonmal jemand darauf hingewiesen, dass man normalerweise die Inverse nicht explizit berechnen braucht.

Ich habe mal für einen movementtracker eine Kovarianzmatrix der Bewegungsabweichungen geschätzt. Diese musste ich dann invertieren um für beliebig viele Objekte die Mahanalobis Distanz zu berechnen (und die ist eben x^TC(-1)x ). Die Alternative wäre gewesen, eine svd zu machen um die Eigenwerte zu kriegen und dann damit rumzufummeln. Aber da kann ich auch gleich invertieren. nimmt sich alles nichts.

Ne andere Sache aus dem Projekt war die Inverse einer Kameramatrix um eine Rückprojektion eines Pixels (mit bekannten Entfernungsdaten) in den 3D-Raum zu vollführen - da das jeden Frame mit 10000 Pixeln gemacht wurde, hatte sich das schon gelohnt. Allerdings wars aber eher faulheit zu invertieren, weil wir alle Parameter hatten um die Inverse Matrix direkt zu berechnen. Aber 30 Zeilen Code vs 1...

otze schrieb:

x^T C^(-1) x

Was spricht dagegen, sich die LU-Zerlegung von C zu merken? Dann kannst Du "C^(-1) x" per Vorwärts- und Rückwärts-Substitution berechnen.

otze

@krümelkacker
Ist das schneller als eine Matrixmultiplikation einer 3x3 Matrix? Numerische Probleme konnten nämlich nicht auftreten

s.luis

Die Inverse muss ich dann mit homogenen Koordinaten multiplizieren und dann wieder auf das kartesische System Rücktransformieren. Damit halt alle Transformationen von meinem Bild gemacht werden können.
Da kommt man nicht so schnell weg von der Inversen, da man diese auf jedes Pixel anwendet!!

Grüße
Luis

Taurin

Deine Matritzen haben eine Größe von 3x3 oder ähnlich klein? Dann ist eh alles egal Da sollte es keine wesentlichen numerischen Probleme geben.

otze schrieb:

@krümelkacker
Ist das schneller als eine Matrixmultiplikation einer 3x3 Matrix? Numerische Probleme konnten nämlich nicht auftreten

Das ist die gleiche Komplexitätsklasse, also O(n^2) bei einer n-kreuz-n Matrix.

s.luis

Taurin schrieb:

Deine Matritzen haben eine Größe von 3x3 oder ähnlich klein? Dann ist eh alles egal Da sollte es keine wesentlichen numerischen Probleme geben.

Ja aber nur mit diesem Input, es können jedoch andere Inputs kommen. Die müssen dann auch behandelt werden.

s.luis

krümelkacker schrieb:

otze schrieb:

@krümelkacker
Ist das schneller als eine Matrixmultiplikation einer 3x3 Matrix? Numerische Probleme konnten nämlich nicht auftreten

Das ist die gleiche Komplexitätsklasse, also O(n^2) bei einer n-kreuz-n Matrix.

Hallo!

Würde ich so nicht unterschreiben!
Bei der einfachen Schulmethode geht es nur mit O(n^3).
Bei der Strassenmethode gehts mit Ω^2.
Ich glaube die schnellste Methode geht zur Zeit mit O(n^2,376)und das ist die Strassenmethode, welche aber nur bei großen Matrizen eingesetzt wird.

Luis

s.luis schrieb:

krümelkacker schrieb:

otze schrieb:

@krümelkacker
Ist das schneller als eine Matrixmultiplikation einer 3x3 Matrix? Numerische Probleme konnten nämlich nicht auftreten

Das ist die gleiche Komplexitätsklasse, also O(n^2) bei einer n-kreuz-n Matrix.

Würde ich so nicht unterschreiben!
Bei der einfachen Schulmethode geht es nur mit O(n^3).
...

Ja, das Berechnen der Inverse bzw das Faktorisieren an sich ist aufwändiger. Es ging aber oben um das Wiederverwenden der inversen Matrix bzw der Faktorisierung.

Walli

s.luis schrieb:

Ich glaube die schnellste Methode geht zur Zeit mit O(n^2,376)und das ist die Strassenmethode, welche aber nur bei großen Matrizen eingesetzt wird.

Nein, das ist der Coppersmith–Winograd Algorithmus. Strassen hat O(n^2,807).

s.luis

Walli schrieb:

s.luis schrieb:

Ich glaube die schnellste Methode geht zur Zeit mit O(n^2,376)und das ist die Strassenmethode, welche aber nur bei großen Matrizen eingesetzt wird.

Nein, das ist der Coppersmith–Winograd Algorithmus. Strassen hat O(n^2,807).

stimmt hast Recht. Wobei der Coppersmith-Winograd-Algo. zum Teil auch von Strassen kommt.

http://www-i1.informatik.rwth-aachen.de/Lehre/SS05/PSAuD/Handout_Grams.pdf

Habe ja auch nicht gewusst wie der Volker Strassen aussieht. Für alle die es interessiert:

http://de.wikipedia.org/wiki/Volker_Strassen

luis