Most stable algorithm to solve a system of linear equations?

I am doing some image processing involving solving a system of linear equations. I am getting some errors and bits of the image looks corrupted. I would like to know what is the most stable way to solve these systems (I don't care how much cpu it takes to compute). It should try to avoid roundoff, catastrophic cancellation, etc.

What would be the most robust algorithm for this?

• Rather than trying to invert $A$ you can try to invert $A + \lambda I$ for some small value of $\lambda$. The the idea is to pad the diagonal enough so that $A$ is much more well-conditioned. There are various algorithms to determine optimal values of $\lambda$, but in practice adding a small $0.001-0.01$ amount should work fine. – Nicholas Mancuso Aug 7 '15 at 22:02
• I am not inverting it at all. I was using guassian elimination. But its ok anyways, I found out how to fix my problem using the more stable quadratic formula here it.uom.gr/teaching/linearalgebra/NumericalRecipiesInC/c5-6.pdf – omega Aug 8 '15 at 5:11
• Use a library rather than writing the code yourself. – Yuval Filmus Aug 8 '15 at 7:53
• @omega Have you tried the LU factorization approach? You can increase the stability of the procedure with pivoting and more so if you use what's called "complete pivoting". If you're interested I can outline the procedure as an answer. I think it is what you're looking for. – Francesco Gramano Aug 15 '15 at 13:47