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]

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.

We have to solve a 9x9 matrix by next Friday for class, I''ll tell you how it goes.

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.

If you end with a row of all 0s then the matrix is non-invertible. So that really isn''t an issue.

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.

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

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]

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]