Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Dirk Gregorius

Determinant and Matrix inversion

This topic is 5370 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi there, I just implemented some easy math stuff and I am wondering how I now could it make more efficient. What are the fastest algorithms for calculating determinants and the inverse of small square matrices like 2x2, 3x3 and 4x4 matrices doing no SIMD or 3DNow assembler programming? And maybe another question. If you write a function like this: Matrix3& Matrix3Transpose(const Matrix3& mtxIn, Matrix3& mtxOut) { // Branch here to avoid overrides if (&mtxIn != &mtxOut) { // No problem - no additional object } else { Matrix temp; // Write everything to temp and the copy to mtxOut mtxOut = temp; // Can we get rid of this? } } Do you branch here for the case that the adress of mtxIn equals mtxOut or is there a way to get rid of the temporary object and the copy? Best regards -Dirk

Share this post


Link to post
Share on other sites
Advertisement
The first thing you'll probably find is some technique in which you step through the matrix diagonally which I can never seem to remember.

There's also a simple recursive algorithm for computing determinants. I'll describe it in a second, but be warned that I'm pretty sure there's a faster algorithm (I'll look for it). Anyway, here goes:

For a square matrix...

For each element in the top row, there is an associated square "sub-matrix" (for lack of a better term), that consists of the original matrix but with the row and column containing that element removed.

The determinant of the matrix is equal to the first element in the top row times the determinant of its corresponding "submatrix" minus the second element of the top row times the determinant of its corresponding "submatrix" plus the third element times its submatrix's determinant, minus the fourth... etc... The signs alternate, plus, minus, plus, minus, etc.

Now, If you started with a 6x6 matrix, then each of the "submatrices" you're dealing with will be 5x5. How do you compute them? The same way; recursively! So then you deal with 4x4 and then 3x3 matrices. Finally, when you get down to 2x2 matrices, you know how to compute the determinant.

Now I'm going to go look for the algorithm I REALLY like...

[edited by - TerranFury on December 16, 2003 1:37:17 PM]

Share this post


Link to post
Share on other sites
The algorithm you described is called cofactor expansion or LaPlace expansion. This is what I implemented. For a 3x3 matrix you end up with 9 muls and 5 adds. For the inverse I tried the Gauss Jordan algoritm but using the loops. I wonder if you can unroll the loops for small matrices and get a performance gain.
And the moment I use the determinant and the adjoints matrix to find the inverse. Premultiplication for 4x4 matrice seems to give a sligth performance gain. Any better ideas?

-Dirk

Share this post


Link to post
Share on other sites
Sounds to me like you''ve got a better handle on this stuff than I do. I now remember that the algorithm that I said I preferred is actually for multiplication, not finding determinants. I''m curious for myself about your question though, so I''m doing a little googling, and if anything interesting turns up I''ll let you know.

Share this post


Link to post
Share on other sites
Not sure about inverses now, but there does seem to be a rather simple technique for quickly computing determinants (versus LaPlace expansion, which is O(n!)).

I found a simple, rather informal description here:
http://acm.uva.es/p/v6/684.html
It brings back dusty memories of tenth-grade math.

Is this Gaussian elimination?

[edited by - TerranFury on December 16, 2003 2:58:39 PM]

Share this post


Link to post
Share on other sites
I think that is cofactor expansion. When I calculated determinants for my math exam I did some easy row or column manipulation such that I get a lot of zero elements in a row or column and then expanded to this row/col. Through the zeros you can get rid of a lot of subdeterminants.

Share this post


Link to post
Share on other sites
Another trick which seems promising is described here: http://mathworld.wolfram.com/LUDecomposition.html

Since the two triangular matrices each have a row which has only one nonzero element, its determinant is the same as that of its corresponding minor. By the same token its minor''s deteminant is the determinant of ITs minor. So one should be able to perform LU decomposition n times to compute the determinant.

Share this post


Link to post
Share on other sites
Gauss Jordan and LUDecomposition are more suited for big matrices. Search for BLAS and LAPACK if your interssted in that stuff. Blitz++ and MTL are also very interessting. From Blitz++ I got the idea which allows you doing this, what is quite cool for checking your routines:

Matrix mtx(3,2);

mtx = 1,2,3,
4,5,5;

This is really handy

-Dirk

Share this post


Link to post
Share on other sites
DonDickieD,

If you want the easy way to calculate the inverse matrix, you need to make sure the matrix is orthogonal. If it is, then all you need to do is transpose it. Do a google search on orthogonal matrices and you''ll find lots of hits, or find a linear algebra book, its sure to have it in there.

-brad

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!