#### Archived

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

# 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.

## 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 on other sites
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 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 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 on other sites
I post the functions here as soon as they are finished. Then we can have a look to together on them.

##### 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 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 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 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 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.

1. 1
Rutin
65
2. 2
3. 3
4. 4
5. 5

• 17
• 10
• 29
• 20
• 9
• ### Forum Statistics

• Total Topics
633415
• Total Posts
3011768
• ### Who's Online (See full list)

There are no registered users currently online

×