Jump to content
  • Advertisement

Archived

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

optics

Invert 4x4 Matrix Gaussian Elimination

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

At this moment I am coding a 4x4 matrix class. I am trying to write an algorithm for doing the inverse using the Gaussian Elimination method. I have found a few ok resources on the internet about this method but nothing that really helps me 100%. I was wondering if anyone has coded a 4x4 matrix class and used gaussian elimination to find the inverse and if so if they would be willing to discuss it with me. Below are some of the links I have found on the subject and a pretty good link on Gauss-Jordan elimination but I have one major problem with the Gauss-Jordan elimination. http://mathworld.wolfram.com/GaussianElimination.html http://www.mcraefamily.com/mathhelp/MatrixReducedRowEchelonForm.htm http://www.rism.com/LinAlg/LAsix.htm http://www.rism.com/LinAlg/LAtwo.htm Thank you for all your help in advance. optics [edited by - optics on March 7, 2004 7:29:13 AM]

Share this post


Link to post
Share on other sites
Advertisement
quote:
Original post by optics
... but I have one major problem with the Gauss-Jordan elimination.


If you mention what the problem is we might be able to help you better.

Share this post


Link to post
Share on other sites
The problem i have with Gauss-Jordan(a simplified version of Gaussian) is that you can end up with a fourth row of 0 0 0 0.

It is hard to mulitply anything by 0 and get 1 for the identity matrix. So this poses a problem for me unless matrices that end up with a 4th row 0 0 0 0 have no determinant.

The problem that I have in coding the algorithm for Gaussian elimination is that everything I find on the internet is that they the pages are mostly theory and not a lot of problem solving. If I could see the Gaussian elimination done on a mock up problem then it would not be that difficult to code. If someone can show me a resource that maybe i missed that works out a sample problem and explains the steps then I could code this algorithm. After I am done then I would be glad to post the source here and also the explanation so that people after me can understand what is going on.

ManBot1: There are NxN matrices classes out there on the internet that would be able to solve your problem. My problem is specific on a 4x4 using Gaussian Elimination. Unless your 9x9 problem will be using the Gaussian Elimination method. If you know a lot about this method or have a resource on it please let me know.

Share this post


Link to post
Share on other sites
If you end with a row of all 0s then the matrix is non-invertible. So that really isn''t an issue.

Share this post


Link to post
Share on other sites
Are you trying to invert an arbitary matrix?
Note that transformation matrices (such as rotation matrices)
are orthogonal and thus can be inverted by simply transposing
them.

In most 3D applications this is what you want so you don''t have
to implement general matrix inversion.


Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Given you''re using a fixed size of 4 x 4 wouldn''t it be just as or similarly efficent to calculate the inverse in the ''classic'' way ? ie:

(1/det(A)) * TRANSFORM( A )

I mean 4x4 is pretty small, you''d avoid any branching code (mis-predictions etc). You''d be looking at 56 mults + 23 sub/add instructions to complete the inversion, and I''m pretty sure if you played arround a bit on paper you could reduce the number of mults...

Share this post


Link to post
Share on other sites
darookie: The matrix is not of arbitrary size.

I was not aware of that for transformation matrices. That may prove to be the quicker route to go but I also want to do this just in case a matrix inversion is necessary on down the road.


Anonymous: I have heard that Gaussian Elimination is a more efficient way of calculating an inverse matrix, although I have not actually been able to test this theory I can not give an exact answer. We will find out when I finish coding this thing.

i will be using an evaluation tool by intel to discover the truth. http://www.gamasutra.com/features/20000131/barad_pfv.htm
at the end of this document is the tool.

On another note if anyone knows the answer to this particular problem on speed, Gaussian Elimination vs. 1/det(A)* Transform (A) Please share with us. It would probably save me some headaches and time.

Thanks.


[edited by - optics on March 7, 2004 7:32:39 AM]

Share this post


Link to post
Share on other sites
Gaussian elimination : less calculations, more memory accesses
(1/det)*adjoint : more calculations, less memory accesses

I can't remember where the turnover point is, but for large matrices the number of calculations required by the (1/det)*adjoint method end up taking more time than the memory accesses for gaussian elimination.

Large matrices : Gaussian elimination is faster
Small matrices : (1/det)*adjoint is faster

I think I remember the (1/det)*adjoint method being faster for 4x4 matrices, but don't quote me on that.


[edited by - joanusdmentia on March 7, 2004 1:55:36 AM]

Share this post


Link to post
Share on other sites
Ok folks. Got the hang of the calculations that are needed to perform the Gaussian elimination however I know that I am not getting the correct form. I feel this way because of this site

http://mathworld.wolfram.com/GaussianElimination.html

What is bugging me is the b1 ... bk part of the equation.
Suppose we have a 4x4 matrix
| e11 e12 e13 e14 |
| e21 e22 e23 e24 |
| e31 e32 e33 e34 |
| e41 e42 e43 e44 |

and we wanted to use Gaussian Elimination to get the matrix in Triangular form
| e11 e12 e13 e14 |
| 0 ~e22 ~e23 ~e24 |
| 0 0 ~e33 ~e34 |
| 0 0 0 ~e44 |

then solve for x1 to xk. I am having a hard time trying to figure out what b1, b2, b3, b4 is suppose to be set to. Do we pull these values out of thin air or is there something I overlooked?

Getting closer to the finish line.



[edited by - optics on March 7, 2004 7:34:06 AM]

[edited by - optics on March 7, 2004 10:55:56 AM]

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!