Sign in to follow this  

inverting matrices

This topic is 4689 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, I need to make a function to invert matrices, I have searched for a while and I found some papers describing two different methods (throught equations and another) I found even some code. What I would like to know are the following things: 1)Should I use a 4*4 matrix inversion algorithm for 4*4 transformation matrices, or can I simply reduce the problem to a 3*3 matrix and them doing some tricks with that? 2)What is the fastest algorithm known for inverting 4*4 (3*3 if previous question was positively answered)? 3)Where can I find some reference about that? Thank you and sorry if I sound a bit boring...

Share this post


Link to post
Share on other sites
A transformation matrix for an object is usually obtained by (resizing,) rotationg and translating the object.

So: M*x = T*R*x
for any point x of the object.

The structure for such a matrix is as follows:


|r11 r12 r13 tx|
|r21 r22 r23 ty|
|r31 r32 r33 tz|
| 0 0 0 1|


where T is

| 1 0 0 tx|
| 0 1 0 ty|
| 0 0 1 tz|
| 0 0 0 1|



and R

|r11 r12 r13 0|
|r21 r22 r23 0|
|r31 r32 r33 0|
| 0 0 0 1|



To calculate the inverse, you have to calculate:

M^-1 = (T*R)^-1 = R^-1 * T^-1

Since R^-1 == transpose(R),
as healeyx76 already mentioned (because R is orthogonal),
you only need to calculate
T^-1 by negating tx, ty and tz.

Then calculate M^-1 as matrix product:

M^-1 = transpose(R) * T^-1

Share this post


Link to post
Share on other sites
For transformation 4x4 matrices, please have a look at the OpenGL Red Book (Programmer's Guide). An early edition is available online, and here is a link to the appendix of interest:

OpenGL Programming Guide

nmi's post basically mirrors this information!

For general matrices, even 4x4's, there are a number of choices. For 4x4 or larger:

A) Cramer's rule: O(n4) operation. Slowest possible way. A really, really bad idea for anything larger than 4x4, but okay for 4x4 or less. Actually, it requires 4 times more floating point operations than Gaussian Elimination even for a 4x4, and it gets vastly worse for larger matrices.

B) Gaussian Elimination: O(n3) operation. A bit faster. Fine for 4x4's and even quite a bit larger. Far too slow for really big matrices. Also, subject to roundoff error which can lead to failure of the algorithm.

C) Iterative methods such as Jacobi, Gauss-Siedel, and Successive Overrelaxation (SOR). Can be very fast, and are superb for sparse matrices. These do not have the same sensitivity to roundoff error that plagues Gaussian Elimination.

D) Other iterative methods...good for more advanced problems.

E) Speciality methods such as the Thomas algorithm for directly solving tridiagonal systems can be extremely fast, but again these aren't for general matrices.

Share this post


Link to post
Share on other sites
Thank you, then I will check for jacobi or one of the other two.

edit: just want to add that the matrix that I need to invert is a LookAt (but a general pourpose algorithm can be useful in the future)

Share this post


Link to post
Share on other sites
Do NOT use an iterative scheme like Jacobi or SOR for inverting a 4x4 LookAt matrix. This is absolute overkill!

Iterative schemes are only good for large sparse matrices. For a small and (almost) full matrix like a LookAt, an iterative scheme is probably much more expensive than Gaussian elimination or Cramer's rule.

I might be wrong about this, but IMHO iterative schemes don't give the inverse matrix M-1 anyway, but only solve some linear system Mx=b for x. That means, you can't really invert a matrix (unless you run the scheme many times using b=unit vector).

Share this post


Link to post
Share on other sites
I've found the following page:
http://www.fnal.gov/docs/working-groups/fpcltf/Pkg/LinearAlgebra/docs/MLDGen-tsntimran.html
it seems that the faster way for a 4x4 matrix is the cofactors method. I think to understand the theory, but I don't know how to calculate efficiently the minor of a 4x4 matrix. If someone has a link to some reference...google gave me a lot of description of the theory, but pretty nothing about an effiecient implementation of this invert algorithm...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
when i was learning sse intrinsics i once came across intels implementation of a matrix inverter for 4x4. 2 methods: gauss, cofactor both "normal" C and using sse intrinsics.
http://www.intel.com/design/pentiumiii/sml/24504301.pdf
this will give you a nice learning experience, imo :)
have fun with it!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
btw: damn off-topic. but i love bolzano!!!!
(i won't do it again, i promise)

Share this post


Link to post
Share on other sites
Thank you for the link (and for loving Bolzano ;-). Sad enaught, I don't know asm (but I'm goin to fill this hole as soon as I finish the curren project (1 year?).

Share this post


Link to post
Share on other sites

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