Finding Inverse of 6x6 Matrix: A Numerical Solution

In summary, a discussion was had regarding finding the inverse of a 6x6 matrix for a computer physics course. The Gauss-Seidel Method, while easily remembered, may be numerically unstable for floating-point values. The suggested method for finding the inverse was through row-reduction, also known as the "row-reduction algorithm". Other suggestions included Gaussian elimination with partial pivoting and LU decomposition. A paper was referenced for further information and it was noted that hard-coding the inverse may be the fastest solution for a 6x6 matrix."
  • #1
Zurtex
Science Advisor
Homework Helper
1,120
1
Hey all :smile:

I have a house mate is doing a computer physics course and he's never before dealt with matrices bigger than 3 x 3. He was wanted to know out how to work out the inverse of 6 x 6, now it's been a long time since I've done this myself. I remembered the Gauss - Seidel Method (where you write out the matrix next to the identity matrix and keep carrying on with elementary row operations) quite easily and showed him that one, however if I remember correctly it is numerically unstable and he is doing a course where he is dealing with floating - point values.

It's just on the edge of my mind, I remember doing a way that you could approximate the inverse through a series of iterative steps, it was heavily paralisable (sp?). If anyone could tell me and perhaps give a quick explanation that I could use to give to him that would be super :biggrin:
 
Mathematics news on Phys.org
  • #2
The best way to find the inverse of a matrix is "row-reduction". Write the matrix A and the identity matrix I side-by-side. Now use row operations to reduce A to the indentity matrix, at each step applying same operation to the matrix beside it. One you have reduced A to I, you will have "reduced" I to A-1. That's true because each row operation corresponds to an "elementary matrix", gotten by doing that row operation to the identity matrix. Reducing A to the identity matrix by row operations is the same as getting the identity matrix by multiplying A by the series of corresponding elementary matrics: in other words, their product is the inverse of A. Applying the same row operations to the identity matrix is the same as multiplying all the corresponding elementary matrices together: the inverse of A.

For more details and examples, look here:
http://tutorial.math.lamar.edu/AllBrowsers/2318/InverseMatrices.asp [Broken]
 
Last edited by a moderator:
  • #3
hallsofivy, I think the point was to find another method besides that, since zurtex doesn't think that works well with floating point values
 
  • #4
Thanks, that's the method I told him, sorry I forgot the name 'row-reduction'. I even calculated that you could come up with an algorithm that at most does 85 additions and 106 multiplications for a 6 x 6 matrix using 'row - reduction'.

However I'm still rather concerned because they are dealing with floating - point operations that this method will be ever so slightly inaccurate. Where as I am sure there was some method where you could iterate and it 'converged' to the inverse matrix, I'm sure also it was actually more efficient if all you wanted was a numerical representation of the inverse matrix (in this case about 20 sf accurate) rather than the actual inverse matrix itself.

I know this sounds awkward and I'm sure if I don't note this, someone will tell me to work with something outside floating point values and then just approximate it. But my friend is working in a language which doesn't have much support and it took them ages just to get 3 x 3 matrices adding together, let along working out inverses of 6 x 6 matrices.
 
  • #5
Hey, I e-mailed a professor at my university and he suggested Gaussian elimination with partial pivoting for solving Ax=b and if I really need to find A-1 then to apply it on the six columns of the identity in turn and apparently that will do.

So I'll take this to my friend and see what he gets :smile:
 
  • #6
If you want an iterative method for solving Ax=b, check out http://en.wikipedia.org/wiki/Generalized_minimal_residual_method" [Broken]
 
Last edited by a moderator:
  • #7
Suppose you symbolically calculated the inverse of a 6x6 matrix and then coded it in the appropriate language. Will this be accomplished in "85 additions and 106 multiplications"? Would this have minimal floating point error? and fastest run time? [Certainly the symbolic suggestion wouldn't be practical with much larger matrices.]
 
  • #8
robphy said:
Suppose you symbolically calculated the inverse of a 6x6 matrix and then coded it in the appropriate language. Will this be accomplished in "85 additions and 106 multiplications"? Would this have minimal floating point error? and fastest run time? [Certainly the symbolic suggestion wouldn't be practical with much larger matrices.]
The point I was trying to make is that this programming language doesn't allow for symbolic approach in the first place...

Actually, the language uses streaming, so I've been trying to familiarise myself with this technique today to try and work out which method is faster with full optimisation of this parallel processing technique.
 
  • #9
A brief search suggests that to invert a matrix, you might want to compute an LU decomposition first... and then invert the triangular matrices.

In fact, here's a paper: Stability of Methods for Matrix Inversion (1992)

But I do want to echo some of the other comments -- does he really want to compute an inverse? Or is he trying to solve some other problem, and thought inversion might be useful? If the latter, there is likely a better way!
 
  • #10
Hurkyl said:
But I do want to echo some of the other comments -- does he really want to compute an inverse? Or is he trying to solve some other problem, and thought inversion might be useful? If the latter, there is likely a better way!

Nope, he really wants to computer an inverse matrix. Some particle physics thing, his supervisor has just told him he needs to be able to efficiently work out the inverse of a matrix in this language that can run on a GPU.

Thanks for the document :smile:
 
  • #11
"LU-GPU: Efficient Algorithms for Solving Dense Linear Systems on Graphics Hardware"
Nico Galoppo Naga K. Govindaraju Michael Henson Dinesh Manocha
University of North Carolina at Chapel Hill
http://gamma.cs.unc.edu/LU-GPU/lugpu05.pdf

If it has to be a 6x6 matrix, then my earlier suggestion of hard-coding it might be faster.
See the middle of http://www.gamedev.net/community/forums/topic.asp?topic_id=180189 from someone who did it for a 4x4 matrix. (The symbolic computation is done once and for all elsewhere [say Maple], then coded in C or whatever language.)
 
Last edited:
  • #12
HallsofIvy said:
The best way to find the inverse of a matrix is "row-reduction". Write the matrix A and the identity matrix I side-by-side. Now use row operations to reduce A to the indentity matrix, at each step applying same operation to the matrix beside it. One you have reduced A to I, you will have "reduced" I to A-1. That's true because each row operation corresponds to an "elementary matrix", gotten by doing that row operation to the identity matrix. Reducing A to the identity matrix by row operations is the same as getting the identity matrix by multiplying A by the series of corresponding elementary matrics: in other words, their product is the inverse of A. Applying the same row operations to the identity matrix is the same as multiplying all the corresponding elementary matrices together: the inverse of A.

For more details and examples, look here:
http://tutorial.math.lamar.edu/AllBrowsers/2318/InverseMatrices.asp
The time is way past my ideal bedtime for tomorrow mornings lecture, I've been staring at my books for a couple of hours now. I came to read that post through a google search and now I finally understand WHY that method for finding inverse matrix's work. It's so obvious, I guess I'm exhausted. Excellent writing, very concise :)

BTW my linear algebra book is terribly, terribly dry and rigorous like you wouldn't imagine (and I usually appreciate rigorousness), yet ommits to write simple little things that would ease the reading and learning process A LOT. I don't really like it. So please do tell if you have any book recommendations on lin.alg.. be it suplementary or a real textbook. I'm thinking about buying this one to read in the summer holidays because of the good user reviews: https://www.amazon.com/dp/0898714540/?tag=pfamazon01-20
 
Last edited by a moderator:
  • #13
Gaco said:
The time is way past my ideal bedtime for tomorrow mornings lecture, I've been staring at my books for a couple of hours now. I came to read that post through a google search and now I finally understand WHY that method for finding inverse matrix's work. It's so obvious, I guess I'm exhausted. Excellent writing, very concise :)

BTW my linear algebra book is terribly, terribly dry and rigorous like you wouldn't imagine (and I usually appreciate rigorousness), yet ommits to write simple little things that would ease the reading and learning process A LOT. I don't really like it. So please do tell if you have any book recommendations on lin.alg.. be it suplementary or a real textbook. I'm thinking about buying this one to read in the summer holidays because of the good user reviews: https://www.amazon.com/dp/0898714540/?tag=pfamazon01-20
Now that I realize my first post did not address the question asked I am mildly embarrased but still will respond to this (I have no shame!).

Every "row operation" has a corresponding "elementary matrix", the matrix you get by applying that row operation to the identity matrix. Performing a given row operation on a matrix is exactly the same as multiplying it by that corresponding elementary matrix. For example, the row operation "multiply every number in the second row by 2" can be done by multiplying by the diagonal matrix having 2 on the second row diagonal position, 1 elsewhere on the diagonal. "Add 2 times the first row to the third" applied to the (3 by 3 for simplicity) identity matrix gives
[tex]\left[\begin{array}{ccc}1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & 0 & 3\end{array}\right][/tex]
elementary matrix and (left) multiplying any matrix by that will "add 2 times the first row to the third".

If you use, say, "k" row operations to reduce matrix A to the identity matrix then you have found k elementary matrices such that [itex](E_kE_{k-1}E_{k-1}\cdot\cdot\cdot E_2E_1)A= I[/itex]. Of course, that equation means that [itex]E_kE_{k-1}E_{k-1}\cdot\cdot\cdot E_2E_1= A^{-1}[/itex]. By applying those row operations to the identity matrix as you work, you have calculated [itex](E_kE_{k-1}E_{k-1}\cdot\cdot\cdotE_2 E_1)I= E_kE_{k-1}E_{k-1}\cdot\cdot\cdot E_2E_1= A^{-1}[/itex].
 
Last edited by a moderator:
  • #14
HallsofIvy said:
Now that I realize my first post did not address the question asked I am mildly embarrased but still will respond to this (I have no shame!).

Every "row operation" has a corresponding "elementary matrix", the matrix you get by applying that row operation to the identity matrix. Performing a given row operation on a matrix is exactly the same as multiplying it by that corresponding elementary matrix. For example, the row operation "multiply every number in the second row by 2" can be done by multiplying by the diagonal matrix having 2 on the second row diagonal position, 1 elsewhere on the diagonal. "Add 2 times the first row to the third" applied to the (3 by 3 for simplicity) identity matrix gives
[tex]\left[\begin{array}{ccc}1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & 0 & 3\end{array}\right][/tex]
elementary matrix and (left) multiplying any matrix by that will "add 2 times the first row to the third".

If you use, say, "k" row operations to reduce matrix A to the identity matrix then you have found k elementary matrices such that [itex](E_kE_{k-1}E_{k-1}\cdot\cdot\cdot E_2E_1)A= I[/itex]. Of course, that equation means that [itex]E_kE_{k-1}E_{k-1}\cdot\cdot\cdot E_2E_1= A^{-1}[/itex]. By applying those row operations to the identity matrix as you work, you have calculated [itex](E_kE_{k-1}E_{k-1}\cdot\cdot\cdotE_2 E_1)I= E_kE_{k-1}E_{k-1}\cdot\cdot\cdot E_2E_1= A^{-1}[/itex].
Oh I did understand it the first time around, I was just expressing my gratitude and relief. Thanks anyway :)
But look now I didn't go to bed promptly, but continued to ponder around something about the dot product.. how stupid of me, I'm going to hate myself tomorrow when the alarm goes.
 
  • #15
"pre-solving" for the inverse via symbolic gaussian elimination (then plugging your particular matrix into the formula you've obtained) is probably a bad idea, depending on how big the matrix is. The reason is that then you can't do any pivoting based on the particular entries of your matrix.

Gaussian elimination with partial pivoting (GEPP) would be good. Say you want to invert A. You would construct PA=LU via GEPP, then invert L and U via back-substitution. GEPP is backwards-stable so long as the growth factor of A is not large, and back-substitution is backwards-stable. Matrices with large growth factors are incredibly rare and never occur in practice. I believe this is the method used by MATLAB.

Gauss-Seidel is an iterative method that is unrelated to gaussian elimination. It will find the inverse, but only if the matrix satisfies certain conditions (diagonally dominant, or somesuch).

As has already been mentioned, modern iterative methods based on Krylov subspaces (such as GMRES already mentioned) are probably best.

A book I highly recommend is Numerical Linear Algebra by Trefethen and Bau. If this is for an immediate application and not just general understanding, one advantage of this book is that it contains pseudocode for all algorithms in addition to the mathematics.
 

1. What is a 6x6 matrix?

A 6x6 matrix is a mathematical object that consists of 6 rows and 6 columns of numbers. It is commonly used in linear algebra and has various applications in engineering, physics, and computer science.

2. Why is finding the inverse of a 6x6 matrix important?

Finding the inverse of a matrix is important because it allows us to solve systems of linear equations, perform transformations, and calculate determinants. Inverse matrices are also used in solving optimization problems and in data analysis.

3. What is the process for finding the inverse of a 6x6 matrix?

The process for finding the inverse of a 6x6 matrix involves using a numerical method, such as Gaussian elimination, to convert the matrix into its reduced row echelon form. The resulting matrix will be the inverse of the original 6x6 matrix.

4. Are there any limitations to finding the inverse of a 6x6 matrix?

Yes, there are limitations to finding the inverse of a 6x6 matrix. For a matrix to have an inverse, it must be a square matrix with a non-zero determinant. If the determinant is zero, the matrix is said to be singular and does not have an inverse.

5. Can the inverse of a 6x6 matrix be found using other methods?

Yes, there are other methods for finding the inverse of a 6x6 matrix, such as using the adjugate matrix or the LU decomposition method. However, these methods may be more complex and time-consuming compared to the numerical method of Gaussian elimination.

Similar threads

Replies
34
Views
2K
  • Programming and Computer Science
Replies
1
Views
2K
  • Precalculus Mathematics Homework Help
Replies
7
Views
2K
  • Atomic and Condensed Matter
Replies
4
Views
1K
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
12
Views
2K
  • Linear and Abstract Algebra
Replies
7
Views
2K
  • Special and General Relativity
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Quantum Physics
Replies
1
Views
781
Back
Top