Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Don’t invert that matrix (2010)

johndcook.com

Post reply on HN
Print view View original

31–40 of 48 posts

Re: Don’t invert that matrix (2010)

#31

Post by x0x0 »

neutronicus wrote: post #28
vvanders wrote: post #2

Is there more context around what exactly he's getting at? In games we use matrix inverses all the time(and since they're usually a specialized affine transform there's cheap shortcuts to calculate them) for stiff like hit detection or animation.

In games you're probably applying many small inverse matrices to many small vectors. In partial differential equations, you solve a single large linear system where the unknown vector represents a field defined at every point on a spatial mesh. In my research, specifically, that spatial mesh can have as many as 10^7 grid points. For linear systems of this size, any exact solution at all is impractical - we exclusivel…

And not only are the matrices small, they're probably known (or assumed) to be well-conditioned.

Inverting even a small hilbert matrix will probably go boom.

Re: Don’t invert that matrix (2010)

#32

Post by jedbrown »

IngoBlechschmid wrote: post #22

That article is quite right regarding the take-home message to try to avoid inverting a matrix when other, more direct methods for solving the particular problem at hand exist. On page 2 of http://www.ti3.tuhh.de/paper/rump/Ru08a.pdf there is an innocent-looking matrix for which the numerically computed inverse is off from the true inverse by 47 orders of magnitude . However, one of the reasons he's given is not corr…

I came here to cite the same paper, but your comment about efficiency is only true in a limited context. Applying an explicitly-computed inverse exposes more parallelism than solving with factors. State of the art parallel linear algebra packages like Elemental (http://libelemental.org) use selective inversion of diagonal blocks to significantly improve their strong scalability.

Re: Don’t invert that matrix (2010)

#33

Post by drauh »

mwfunk wrote: post #4

I get that inverting a matrix can be computationally intensive, but what's the alternative? "What if you have to solve Ax = b for a lot of different b‘s? Surely then it’s worthwhile to find A-1. No. The first time you solve Ax = b, you factor A and save that factorization. Then when you solve for the next b, the answer comes much faster." I don't get it, although I'm not a numerics expert so maybe I'm missing somethi…

http://www.amazon.com/Applied-Numerical-Linear-Algebra-Demme...

Numerical linear algebra has a long and vast history. You really do need specialized information that your undergrad linear algebra classes would not have imparted.

For instance, the condition number is important: https://en.wikipedia.org/wiki/Condition_number

Re: Don’t invert that matrix (2010)

#34

Post by IngoBlechschmid »

jedbrown wrote: post #32
IngoBlechschmid wrote: post #22

That article is quite right regarding the take-home message to try to avoid inverting a matrix when other, more direct methods for solving the particular problem at hand exist. On page 2 of http://www.ti3.tuhh.de/paper/rump/Ru08a.pdf there is an innocent-looking matrix for which the numerically computed inverse is off from the true inverse by 47 orders of magnitude . However, one of the reasons he's given is not corr…

I came here to cite the same paper, but your comment about efficiency is only true in a limited context. Applying an explicitly-computed inverse exposes more parallelism than solving with factors. State of the art parallel linear algebra packages like Elemental ( http://libelemental.org ) use selective inversion of diagonal blocks to significantly improve their strong scalability.

Thank you for sharing that insight! Didn't know that.

Re: Don’t invert that matrix (2010)

#36

Post by [deleted] »

donuteaters wrote: post #23
mwfunk wrote: post #4

I get that inverting a matrix can be computationally intensive, but what's the alternative? "What if you have to solve Ax = b for a lot of different b‘s? Surely then it’s worthwhile to find A-1. No. The first time you solve Ax = b, you factor A and save that factorization. Then when you solve for the next b, the answer comes much faster." I don't get it, although I'm not a numerics expert so maybe I'm missing somethi…

You calculate the factorization (QR, LU, or similar), but you never calculate the inverse of the factorization: A x = b A => QR # QR decomposition Q R x = b R x = Q' b # Q is inverted by transposing x = backsubstitute(R, Q' b) Q was the transpose of it's inverse, and so you don't get any rounding error when you transpose it. R didn't need to be inverted because it was in a form where back substitution lets you apply…

[deleted]

Re: Don’t invert that matrix (2010)

#37

Post by pramodliv1 »

donuteaters wrote: post #23
mwfunk wrote: post #4

I get that inverting a matrix can be computationally intensive, but what's the alternative? "What if you have to solve Ax = b for a lot of different b‘s? Surely then it’s worthwhile to find A-1. No. The first time you solve Ax = b, you factor A and save that factorization. Then when you solve for the next b, the answer comes much faster." I don't get it, although I'm not a numerics expert so maybe I'm missing somethi…

You calculate the factorization (QR, LU, or similar), but you never calculate the inverse of the factorization: A x = b A => QR # QR decomposition Q R x = b R x = Q' b # Q is inverted by transposing x = backsubstitute(R, Q' b) Q was the transpose of it's inverse, and so you don't get any rounding error when you transpose it. R didn't need to be inverted because it was in a form where back substitution lets you apply…

MATLAB's linsolve uses your strategy! (http://in.mathworks.com/help/matlab/ref/linsolve.html)

Re: Don’t invert that matrix (2010)

#38

Post by hchenji »

mwfunk wrote: post #4

I get that inverting a matrix can be computationally intensive, but what's the alternative? "What if you have to solve Ax = b for a lot of different b‘s? Surely then it’s worthwhile to find A-1. No. The first time you solve Ax = b, you factor A and save that factorization. Then when you solve for the next b, the answer comes much faster." I don't get it, although I'm not a numerics expert so maybe I'm missing somethi…

Use a Pseudoinverse or a decomposition instead. A great book to read is Matrix Computations by Golub/van Loan.

Re: Don’t invert that matrix (2010)

#39

Post by cpburns2009 »

rsp1984 wrote: post #27

It's funny because the whole discussion only exists because there is no division operator in "matrix math". For scalars we can simply write a / b (instead of a^-1 * b) and everyone knows how to calculate it. But for some reason there's no such thing when dealing with matrices. Well it turns out there is something like division for matrices and it's called factorization (followed by back-substitution) and there are ac…

I think you meant "b / a" in "a / b (instead of a^-1 * b)".

Re: Don’t invert that matrix (2010)

#40

Post by jacobolus »

cpburns2009 wrote: post #39
rsp1984 wrote: post #27

It's funny because the whole discussion only exists because there is no division operator in "matrix math". For scalars we can simply write a / b (instead of a^-1 * b) and everyone knows how to calculate it. But for some reason there's no such thing when dealing with matrices. Well it turns out there is something like division for matrices and it's called factorization (followed by back-substitution) and there are ac…

I think you meant "b / a" in "a / b (instead of a^-1 * b)".

By b / A he is implying a horizontal fraction bar with b above and A below. Of course, since matrix multiplication is not commutative, it’s probably better to write something like /A * b (or Matlab uses the cute notation A \ b) instead of b / A, but the intention is fairly clear from context.

(In general, most of our mathematical notation conventions are designed for the real number system, and start falling over when we have “number-like objects” which behave a bit differently.)

Post reply on HN