Sign in to follow this  

Matrix Inverse

This topic is 4734 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

Can someone please shed some light on getting the inverse of a matrix(4x4)....i am not totally clear on it and i have hit google hard but i cant make heads nor tails of it...can someone dumb it down a notch

Share this post


Link to post
Share on other sites
Probably the easiest way to get the inverse (at least to visualize) is to start with a 4x8 matrix, with the 4x4 matrix you want to invert on the left hand side, and the 4x4 identity matrix on the right hand side like:

[ a b c d 1 0 0 0 ]
[ e f g h 0 1 0 0 ]
[ i j k l 0 0 1 0 ]
[ m n o p 0 0 0 1 ]

From there, you do row operations (swaps, row additions and scalar multiplication) to try to get the left hand side to look like the identity matrix. For example, if a is non-zero, you might divide the first row by a to get:

[ 1 b' c' d' 1/a 0 0 0 ]
[ e f g h 0 1 0 0 ]
[ i j k l 0 0 1 0 ]
[ m n o p 0 0 0 1 ]

Then subtract e times the first row from the second row to get:

[ 1 b' c' d' 1/a 0 0 0 ]
[ 0 f' g' h' -e/a 1 0 0 ]
[ i j k l 0 0 1 0 ]
[ m n o p 0 0 0 1 ]

Do the same thing with the third and fourth rows to get:

[ 1 b' c' d' 1/a 0 0 0 ]
[ 0 f' g' h' -e/a 1 0 0 ]
[ 0 j' k' l' -i/a 0 1 0 ]
[ 0 n' o' p' -m/a 0 0 1 ]

Now try to get the second column to look like 0 1 0 0, so you might divide the second row by f' and subtract multiples of the second row from all the other rows. Eventually you'll end up with something that looks like:

[ 1 0 0 0 a'' b'' c'' d'' ]
[ 0 1 0 0 e'' f'' g'' h'' ]
[ 0 0 1 0 i'' j'' k'' l'' ]
[ 0 0 0 1 m'' n'' o'' p'' ]

And the right hand side will be the inverse you were trying to find.

There are a couple of things to watch out for if you do this. Sometimes you'll have a zero in the diagonal where you're trying to get a 1. In that case, swap the row with another lower row where it doesn't have a 0 there. If there isn't a row that doesn't have a 0, then the matrix is non-invertible. Also, you can get some bad rounding problems using a straightforward implementation of this technique, so it's not recommended for general use in finding matrix inverses.

Share this post


Link to post
Share on other sites
I believe CoFactors come into play with the Cramer's Rule approach, which is a poor approach----extremely expensive if the matrix is larger than 4x4.

Can you shed some light on exactly why you need the inverse? The game development uses of the inverse should be mostly well covered, even in the forum archives here (which are searchable).

Share this post


Link to post
Share on other sites
I have exactly what you need...

you have "m" arranged as thus:
m =
[ m11, m12, m13, m14]
[ m21, m22, m23, m24]
[ m31, m32, m33, m34]
[ m41, m42, m43, m44]

then its inverse is the following

inverse( m ) =
[ m22*m33*m44-m22*m34*m43-m32*m23*m44+m32*m24*m43+m42*m23*m34-m42*m24*m33, -m12*m33*m44+m12*m34*m43+m32*m13*m44-m32*m14*m43-m42*m13*m34+m42*m14*m33, m12*m23*m44-m12*m24*m43-m22*m13*m44+m22*m14*m43+m42*m13*m24-m42*m14*m23, -m12*m23*m34+m12*m24*m33+m22*m13*m34-m22*m14*m33-m32*m13*m24+m32*m14*m23]
[ -m21*m33*m44+m21*m34*m43+m31*m23*m44-m31*m24*m43-m41*m23*m34+m41*m24*m33, m11*m33*m44-m11*m34*m43-m31*m13*m44+m31*m14*m43+m41*m13*m34-m41*m14*m33, -m11*m23*m44+m11*m24*m43+m21*m13*m44-m21*m14*m43-m41*m13*m24+m41*m14*m23, m11*m23*m34-m11*m24*m33-m21*m13*m34+m21*m14*m33+m31*m13*m24-m31*m14*m23]
[ m21*m32*m44-m21*m34*m42-m31*m22*m44+m31*m24*m42+m41*m22*m34-m41*m24*m32, -m11*m32*m44+m11*m34*m42+m31*m12*m44-m31*m14*m42-m41*m12*m34+m41*m14*m32, m11*m22*m44-m11*m24*m42-m21*m12*m44+m21*m14*m42+m41*m12*m24-m41*m14*m22, -m11*m22*m34+m11*m24*m32+m21*m12*m34-m21*m14*m32-m31*m12*m24+m31*m14*m22]
[ -m21*m32*m43+m21*m33*m42+m31*m22*m43-m31*m23*m42-m41*m22*m33+m41*m23*m32, m11*m32*m43-m11*m33*m42-m31*m12*m43+m31*m13*m42+m41*m12*m33-m41*m13*m32, -m11*m22*m43+m11*m23*m42+m21*m12*m43-m21*m13*m42-m41*m12*m23+m41*m13*m22, m11*m22*m33-m11*m23*m32-m21*m12*m33+m21*m13*m32+m31*m12*m23-m31*m13*m22]

as much as it appears ugly and unintuitive, it is by far faster than any other method especially if you spot recurrent muls and assign them into variables...

general methods however should be considered when working with other than 4x4 matrices (uncommon with 3d game programming however)

enjoy

Share this post


Link to post
Share on other sites
Quote:
Original post by BrainCodingArts
I have exactly what you need...

you have "m" arranged as thus:
m =
[ m11, m12, m13, m14]
[ m21, m22, m23, m24]
[ m31, m32, m33, m34]
[ m41, m42, m43, m44]

then its inverse is the following

...

as much as it appears ugly and unintuitive, it is by far faster than any other method especially if you spot recurrent muls and assign them into variables...

general methods however should be considered when working with other than 4x4 matrices (uncommon with 3d game programming however)

enjoy

You need to divide the elements of the matrix by the determinant of m after that big block of math, or if the determinant comes out to be 0 (do this before finding the adjugate), just skip out or throw an exception or something because it is not invertable. What you have there is the adjugate, which is the transpose of the matrix of the cofactors (phew ;))

Share this post


Link to post
Share on other sites
Quote:
Original post by BrainCodingArts
as much as it appears ugly and unintuitive, it is by far faster than any other method especially if you spot recurrent muls and assign them into variables...


Actually, that method is not faster than other methods. In fact, its the slowest method. This appears to be a fragment of the Cramer's rule method. 4x4 is absolutely the largest matrix you would EVER want to apply Cramer's rule to. This is an n4 operation. Yes, you read correctly, its an n-to-the-FOURTH operation. That means a 4x4 matrix inverse requires O(256) multiply/divide/add/subtract operations (count them in your equation). In contrast, naive Gaussian Elimination, a n3 operation is far cheaper, requiring only O(64) operations. I only point this out in the interest of education, :).

I will give you this. For some types of matrices (symmetric matrices) there can be recurrent operations that can be cached and reused, thus reducing the expense of Cramer's rule. But, the general fact is that it is by far the slowest technique. Might as well code up one of the other methods.

The following web page has a more in depth discussion. Note especially the table comparing the expansion by minors bit of Cramer's rule to Gaussian Elimination:

Operation Counts

[Edited by - grhodes_at_work on December 27, 2004 1:57:32 PM]

Share this post


Link to post
Share on other sites
but, in that Intel paper i referred to, 4x4 Cramer's rule is faster. Gaussian elimination requirs branching, and every branch costs as several multiplies. Of course, on bigger matrices Gaussian elimination is much faster, but probably because of cost of branching, 4x4 Cramer's is faster.....

Share this post


Link to post
Share on other sites
Quote:
Original post by Dmytry
but, in that Intel paper i referred to, 4x4 Cramer's rule is faster. Gaussian elimination requirs branching, and every branch costs as several multiplies. Of course, on bigger matrices Gaussian elimination is much faster, but probably because of cost of branching, 4x4 Cramer's is faster.....


Oh, right, right you are, :). I remember that paper now, from a couple of years ago. However, remember that this result is platform specific. Might see the same result on CPU's with similar features...

Share this post


Link to post
Share on other sites
There is more too it than just what the theoretical run time is. Floating point multiplications and additions are very computationally inexpensive whereas branches are. It would be nice if someone would test but I'm pretty sure that the Cramer's rule is faster here.

Share this post


Link to post
Share on other sites

This topic is 4734 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this