# Inverse Matrix

1. Nov 2, 2006

### Zurtex

Hey all

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

2. Nov 3, 2006

### HallsofIvy

Staff Emeritus
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

3. Nov 3, 2006

### Office_Shredder

Staff Emeritus
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. Nov 3, 2006

### Zurtex

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. Nov 3, 2006

### Zurtex

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

6. Nov 3, 2006

If you want an iterative method for solving Ax=b, check out GMRES

7. Nov 3, 2006

### robphy

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. Nov 4, 2006

### Zurtex

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. Nov 4, 2006

### Hurkyl

Staff Emeritus
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. Nov 5, 2006

### Zurtex

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

11. Nov 5, 2006

### robphy

"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: Nov 5, 2006
12. Dec 11, 2008

### Gaco

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: http://www.amazon.com/Matrix-Analysis-Applied-Algebra-Solutions/dp/0898714540

Last edited: Dec 11, 2008
13. Dec 11, 2008

### HallsofIvy

Staff Emeritus
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
$$\left[\begin{array}{ccc}1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & 0 & 3\end{array}\right]$$
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 $(E_kE_{k-1}E_{k-1}\cdot\cdot\cdot E_2E_1)A= I$. Of course, that equation means that $E_kE_{k-1}E_{k-1}\cdot\cdot\cdot E_2E_1= A^{-1}$. By applying those row operations to the identity matrix as you work, you have calculated $(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}$.

Last edited: Dec 11, 2008
14. Dec 11, 2008

### Gaco

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 gonna hate myself tomorrow when the alarm goes.

15. Dec 11, 2008

### maze

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