神刀安全网

Don't invert that matrix

There is hardly ever a good reason to invert a matrix.

What do you do if you need to solve Ax = b where A is an n x n matrix? Isn’t the solution A -1 b ? Yes, theoretically. But that doesn’t mean you need to actually find A -1 . Solving the equation Ax = b is faster than finding A -1 . Books might write the problem as x = A -1 b , but that doesn’t mean they expect you to calculate it that way.

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. (Factorization takes O( n 3 ) operations. But once the matrix is factored, solving Ax = b takes only O( n 2 ) operations. Suppose n = 1,000. This says that once you’ve solved Ax = b for one b , the equation can be solved again for a new b 1,000 times faster than the first one. Buy one get one free.)

What if, against advice, you’ve computed A -1 . Now you might as well use it, right? No, you’re still better off solving Ax = b than multiplying by A -1 , even if the computation of A -1 came for free. Solving the system is more numerically accurate than the performing the matrix multiplication.

It is common in applications to solve Ax = b even though there’s not enough memory to store A -1 . For example, suppose n = 1,000,000 for the matrix A but A has a special sparse structure — say it’s banded — so that all but a few million entries of A are zero.  Then A can easily be stored in memory and Ax = b can be solved very quickly. But in general A -1 would be dense. That is, nearly all of the 1,000,000,000,000 entries of the matrix would be non-zero.  Storing A requires megabytes of memory, but storing A -1 would require terabytes of memory.

Don't invert that matrix

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Don't invert that matrix

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址