[Numerical] Why is it better to solve Ax=b instead of calculating inv(A)

nonequilibrium

Hello,

So I'm using a numerical method where I iteratively have to solve [itex]Ax_{i+1}=x_i[/itex] which can of course be done by calculating the inverse matrix, but something in the back of my mind is telling me that it is better to solve the equation using Gaussian elimination and substitution.

However, what is the reason for this? And is the difference relevant, or is merely a difference "in principle".

D H

There are lots of reasons not to use the inverse. Stability, accuracy, time. However, some of these reasons apply to a one-time solution of [itex]Ax=b[/itex]. Here you are apparently reusing the A matrix, iteratively solving [itex]Ax_{i+1} = x_i[/itex]. If you reuse A, timing considerations suggest you should compute the inverse of A instead of using Gaussian elimination.

There's an even better approach to using either of the techniques you mentioned. Compute the LU decomposition. It's cheaper to compute the LU decomposition than it is to use Gaussian elimination or the matrix inverse. LU backsubstitution is fast, faster than the matrix * vector computation, and the same stability and accuracy advantages that pertain to Gaussian elimination apply to LU decomposition.

nonequilibrium

The iteration usually takes only three steps though, so maybe it is not evident that the inverse is optimal relative to solving it by Gaussian elimination?

Interesting what you say about the LU decomposition...

AlephZero

Calculating the inverse efficiently (i.e. by doing an LU decomposition and then solving N right hand sides each containng one 1 and the rest of the entries 0) is an overhead of about N solves. So if you are only doing 3 solves anyway, you will lose unless N is very small.

In addition to D.H's points, often A is sparse and the LU decomposition has a similar amount of sparsity, but the inverse matrix is almost always fully populated. In that situation, multiplying by the inverse can be orders of magnitude more expensive than solving using the sparse matrices, quite apart from the numerical conditoning issues and the amount of storage that may be required for the inverse matrix.

My "rule of thumb" here is that explicitly inverting a matrix numerically is NEVER the right thing to do, unless you can make a very good argument in favor of it. Even when it appears to be "no worse" than equation solving, straightforward equation solving (based on LU decomoposition for example) is usually not the only alternative.

nonequilibrium

Thank you both for the good advice.