How to solve $Ax=b$ wihout inverting $A$?

Question

I'm going to solve this equation:

$$Ax=b$$

Onto an embedded system with using C-programing language. It need to be fast as possible. Assume that $A$ is not square. One way to solve this is to use:

$$x = (A^TA)^{-1}A^T b$$

But I have heard from this page that solving $Ax=b$ should not be done by inverting $A$.

What do you do if you need to solve $Ax = b$, where $A$ is an $n \times 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.

https://www.johndcook.com/blog/2010/01/19/dont-invert-that-matrix/

So is there any method to solve $Ax=b$ without inverting $A$? I'm talking about

$$\min (Ax-b = 0)$$

Answer 1

You are asking for 2 different problems. If you need to solve $Ax=b$, and output no solution when no solution exists, a good first stop is Gaussian Elimination.

If you need to find $\min_x \|Ax-b\|^2$, you are looking for linear least squares solver.