4. Optimierung?

Optimierung?

  • ?

    Hi,

    ich habe folgende Funktion, doch die ist MEGA LAM, drum frag ich einfach mal obs ne vereinfachung gibt eine inverse-matrix zu berechnen:

    __forceinline bool getInverse (matrix& out)
    {
            // Calculates the inverse of this Matrix 
            // The inverse is calculated using Cramers rule.
            // If no inverse exists then 'false' is returned.
        const matrix &m (*this);

        float d = (m(0, 0)*m(1, 1) - m(1, 0)*m(0, 1))*(m(2, 2)*m(3, 3) - m(3, 2)*m(2, 3)) - (m(0, 0)*m(2, 1) - m(2, 0)*m(0, 1))*(m(1, 2)*m(3, 3) - m(3, 2)*m(1, 3))
                + (m(0, 0)*m(3, 1) - m(3, 0)*m(0, 1))*(m(1, 2)*m(2, 3) - m(2, 2)*m(1, 3)) + (m(1, 0)*m(2, 1) - m(2, 0)*m(1, 1))*(m(0, 2)*m(3, 3) - m(3, 2)*m(0, 3))
                - (m(1, 0)*m(3, 1) - m(3, 0)*m(1, 1))*(m(0, 2)*m(2, 3) - m(2, 2)*m(0, 3)) + (m(2, 0)*m(3, 1) - m(3, 0)*m(2, 1))*(m(0, 2)*m(1, 3) - m(1, 2)*m(0, 3));

        if (d == 0.f)
            return (false);

        d = 1 / d;
        out(0, 0) = d*(m(1, 1)*(m(2, 2)*m(3, 3) - m(3, 2)*m(2, 3)) + m(2, 1)*(m(3, 2)*m(1, 3) - m(1, 2)*m(3, 3)) + m(3, 1)*(m(1, 2)*m(2, 3) - m(2, 2)*m(1, 3)));
        out(1, 0) = d*(m(1, 2)*(m(2, 0)*m(3, 3) - m(3, 0)*m(2, 3)) + m(2, 2)*(m(3, 0)*m(1, 3) - m(1, 0)*m(3, 3)) + m(3, 2)*(m(1, 0)*m(2, 3) - m(2, 0)*m(1, 3)));
        out(2, 0) = d*(m(1, 3)*(m(2, 0)*m(3, 1) - m(3, 0)*m(2, 1)) + m(2, 3)*(m(3, 0)*m(1, 1) - m(1, 0)*m(3, 1)) + m(3, 3)*(m(1, 0)*m(2, 1) - m(2, 0)*m(1, 1)));
        out(3, 0) = d*(m(1, 0)*(m(3, 1)*m(2, 2) - m(2, 1)*m(3, 2)) + m(2, 0)*(m(1, 1)*m(3, 2) - m(3, 1)*m(1, 2)) + m(3, 0)*(m(2, 1)*m(1, 2) - m(1, 1)*m(2, 2)));
        out(0, 1) = d*(m(2, 1)*(m(0, 2)*m(3, 3) - m(3, 2)*m(0, 3)) + m(3, 1)*(m(2, 2)*m(0, 3) - m(0, 2)*m(2, 3)) + m(0, 1)*(m(3, 2)*m(2, 3) - m(2, 2)*m(3, 3)));
        out(1, 1) = d*(m(2, 2)*(m(0, 0)*m(3, 3) - m(3, 0)*m(0, 3)) + m(3, 2)*(m(2, 0)*m(0, 3) - m(0, 0)*m(2, 3)) + m(0, 2)*(m(3, 0)*m(2, 3) - m(2, 0)*m(3, 3)));
        out(2, 1) = d*(m(2, 3)*(m(0, 0)*m(3, 1) - m(3, 0)*m(0, 1)) + m(3, 3)*(m(2, 0)*m(0, 1) - m(0, 0)*m(2, 1)) + m(0, 3)*(m(3, 0)*m(2, 1) - m(2, 0)*m(3, 1)));
        out(3, 1) = d*(m(2, 0)*(m(3, 1)*m(0, 2) - m(0, 1)*m(3, 2)) + m(3, 0)*(m(0, 1)*m(2, 2) - m(2, 1)*m(0, 2)) + m(0, 0)*(m(2, 1)*m(3, 2) - m(3, 1)*m(2, 2)));
        out(0, 2) = d*(m(3, 1)*(m(0, 2)*m(1, 3) - m(1, 2)*m(0, 3)) + m(0, 1)*(m(1, 2)*m(3, 3) - m(3, 2)*m(1, 3)) + m(1, 1)*(m(3, 2)*m(0, 3) - m(0, 2)*m(3, 3)));
        out(1, 2) = d*(m(3, 2)*(m(0, 0)*m(1, 3) - m(1, 0)*m(0, 3)) + m(0, 2)*(m(1, 0)*m(3, 3) - m(3, 0)*m(1, 3)) + m(1, 2)*(m(3, 0)*m(0, 3) - m(0, 0)*m(3, 3)));
        out(2, 2) = d*(m(3, 3)*(m(0, 0)*m(1, 1) - m(1, 0)*m(0, 1)) + m(0, 3)*(m(1, 0)*m(3, 1) - m(3, 0)*m(1, 1)) + m(1, 3)*(m(3, 0)*m(0, 1) - m(0, 0)*m(3, 1)));
        out(3, 2) = d*(m(3, 0)*(m(1, 1)*m(0, 2) - m(0, 1)*m(1, 2)) + m(0, 0)*(m(3, 1)*m(1, 2) - m(1, 1)*m(3, 2)) + m(1, 0)*(m(0, 1)*m(3, 2) - m(3, 1)*m(0, 2)));
        out(0, 3) = d*(m(0, 1)*(m(2, 2)*m(1, 3) - m(1, 2)*m(2, 3)) + m(1, 1)*(m(0, 2)*m(2, 3) - m(2, 2)*m(0, 3)) + m(2, 1)*(m(1, 2)*m(0, 3) - m(0, 2)*m(1, 3)));
        out(1, 3) = d*(m(0, 2)*(m(2, 0)*m(1, 3) - m(1, 0)*m(2, 3)) + m(1, 2)*(m(0, 0)*m(2, 3) - m(2, 0)*m(0, 3)) + m(2, 2)*(m(1, 0)*m(0, 3) - m(0, 0)*m(1, 3)));
        out(2, 3) = d*(m(0, 3)*(m(2, 0)*m(1, 1) - m(1, 0)*m(2, 1)) + m(1, 3)*(m(0, 0)*m(2, 1) - m(2, 0)*m(0, 1)) + m(2, 3)*(m(1, 0)*m(0, 1) - m(0, 0)*m(1, 1)));
        out(3, 3) = d*(m(0, 0)*(m(1, 1)*m(2, 2) - m(2, 1)*m(1, 2)) + m(1, 0)*(m(2, 1)*m(0, 2) - m(0, 1)*m(2, 2)) + m(2, 0)*(m(0, 1)*m(1, 2) - m(1, 1)*m(0, 2)));

        return (true);
    }
    0
  • J

    Hui, das sieht nach ner großen Fleißarbeit aus.

    Generell würde ich mal sagen: ohne genauere Angaben kann man die Matrix wohl nicht viel schneller invertieren.

    Muß das denn für beliebige Matrizen funktionieren? Oder haben die eine bestimmte Struktur? Dafür gibt es nämlich oftmals spezialisierte Algorithmen die deutlich schneller sind.

    Hast Du's mal mit irgendeinem Algebra-Package versucht? Bei boost ist inzwischen glaub ich auch sowas dabei.

    Und dann natürlich noch die wichtige Frage: mußt Du die Matrix wirklich invertieren?
    Ein Dozent von mir sagte mal: "Invertieren Sie nie eine Matrix!" Wenn es irgendeine Möglichkeit gibt das anders zu lösen, dann ist die wahrscheinlich besser.

    MfG Jester

    0
  • F

    Ich weiß zwar nicht, ob es für n=4 schneller wird als deine Funktion,
    aber für n bel. rechnet man die Inverse einer Matrix aus, indem man
    die Matrix A zerlegt in A = LU und dann für i = 1...n das LGS
    Ax=LUx=eiAx = LUx = e_i löst, wobei eie_i der i-te Einheitsvektor sein soll.

    Ich denke, da müßte sich was im Internet auftreiben lassen ...

    0
  • ?

    es ist eine 4x4 matrix:

    class matrix
{
public:
   // ...
    union 
    {
        struct { float _11, _12, _13, _14; 
                 float _21, _22, _23, _24; 
                 float _31, _32, _33, _34; 
                 float _41, _42, _43, _44; };
        struct { float values[16]; };
    };
    0
  • J

    Das hat keiner bezweifelt.

    0
  • F

    Doch, ich anscheinend, kann heute nur bis 3 zählen. Werds mal ändern.
    Äh, ja, hier noch ein Link zu verschiedenen Bibliotheken: http://www.oonumerics.org/oon/

    Und wofür genau brauchst du das jetzt genau? Wie Jester ja schon sagte, kann man die Berechnung einer Inversen meistens umgehen.

    0
  • ?

    für transformierungen in andere koordiantensysteme und kollisionsabfragen

    0
  • J

    Hm, das ist in der Tat einer der Fälle wo man die Inverse oftmals benötigt. Allerdings ist die Frage, ob es so wichtig ist wie schnell die Funktion ist. Der Normalfall ist hier eher der, daß man eine Matrix invertiert und dann einige 1000 Punkte damit überprüft... und dann ist der Anteil der Zeit der zum invertieren benötigt wird ziemlich uninteressant.

    Aber bei solchen Transformationen hat man oft ne gute Matrix-Struktur.

    Ist es eine Rotation? => die Rotation um die gleiche Achse mit negativem Drehwinkel ist die Inverse. Verschiebung? => umgekehrte Verschiebung ist die Inverse
    Skalierung? => mit den Kehrwerten skalieren.

    Ist es eine Kombination dieser Transformationen, dann einfach die Zerlegung betrachten (hat man zumeist, da man so an die Matrix gekommen ist) und jede Einzelmatrix für sich invertieren (s.o.) und dann in umgekehrter Reihenfolge zusammenmultiplizieren. Das ist dann die Inverse. Das macht zum Beispiel Sinn, wenn man nen Baum runter steigt wo immer mehr Matrizen aufmultipliziert werden und man braucht auf jeder Ebene die Inverse. Dann braucht man immer nur ne Matrixmultiplikation.

    MfG Jester

    0
  • K

    Für Intel und AMD-Athlon CPU's kannst Du SSE verwenden. In diesem
    ftp://download.intel.com/design/pentiumiii/sml/24504301.pdf
    Paper von Intel steht wie; mit Source.

    Da steht Performancesteigerung um Faktor 4 auf 'nem P3. Kannst Du ja mal testen und dann hier beschreiben wieviel es bringt 🙂 .

    Gruß
    Michael

    0
  • B

    http://www.c-plusplus.net/forum/viewtopic.php?t=66412&highlight=
    das ist das schnellste für Trf denn da braucht man als inverse nur die Transponierte.

    0
  • ?

    Und noch ein 'Google-Tipp': Pseudo-Inverse.

    Das sind schnell berechenbare Matrzen - mit ähnlichen Eigenschaften wie
    die echten Inversen - nur schneller zu berechenen.

    Jockel

    0
Anmelden zum Antworten