Boost und inverse Matrix

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