# A fast way to check if a Matrix is ill-conditioned, and turning it into well-conditioned

I'm running a simulation, and some linear solvers are returning a message of ill-conditioned matrix.

Hence, I'm looking for a fast, easy to implement, method to detect if a matrix is ill-conditioned, before using the linear solver. And in case it's ill-conditioned, what's good way to make it well-conditioned?

• You need to understand at a higher level why your system of equations is ill-conditioned. The proper solution will almost certainly lie within the process that is generating these systems of equations. – Brian Borchers Apr 15 '19 at 15:11
• The method of letting LU-decomposition (with or without pivoting) run its course is a valid way of checking whether the matrix is ill-conditioned. The other measures common to NLA are actually more expensive. On the practical side I agree with @BrianBorchers – Nox Apr 15 '19 at 20:53
• I will third this: If the matrix you have in your linear system is ill-conditioned, then it is ill-conditioned. If you want to change the matrix, you change the linear system, so you get a solution to a different problem. You need to find out why it is ill-conditioned, not patch over it. – Wolfgang Bangerth Apr 17 '19 at 3:04
• @BrianBorchers please, can you expand your comment? I would be particularly interested in inverse problems. In these cases can you improve the generating process? Or you must work with regularization? – Mauro Vanzetto May 5 '19 at 17:42
• @MauroVanzetto: Preconditioning is for poorly conditioned matrices, i.e., with bad but not terrible condition numbers. But when a linear solver says that the matrix is ill-conditioned, then that's often an indication that one is either using a poorly chosen formulation, or that there is a bug in the code. In either case, it's important to understand the cause of the conditioning, not to paper over it. – Wolfgang Bangerth May 7 '19 at 13:06

To detect if a matrix is ill-conditioned you can check the condition number defined, for the matrix $$A$$ as: $$k(A) = ||A|| \, ||A^{-1}||$$

For norm 2 this is equal to the ratio of singular values: $$k(A) = \frac{\sigma_{max}(A)}{\sigma_{min}(A)}$$

Numerically there are also other methods to estimate $$k(A)$$. For more details see chapter 15 of [1], and [2] where you can find source code for different methods (Hager, from LINPACK, sampling) in different languages.

To threat an ill-conditioned system there are two principal ways:

preconditioning: using this technique you obtain a system mathematically equivalent to the start situation, but with a better condition number. The methods depend on the structure of the matrix that you have, but you can see for example [3] for iterative methods.

regularization: here you obtain an approximation of the starter system, these methods work also for ill-posed problem. Example of techniques in this family are:

For more details and references see for example [4].

[1] Higham, Nicholas J., Accuracy and stability of numerical algorithms., Philadelphia, PA: SIAM. xxx, 680 p. (2002). ZBL1011.65010.

[2] web page Matrix Condition Number Estimation

[3] Saad, Yousef, Iterative methods for sparse linear systems., Philadelphia, PA: SIAM Society for Industrial and Applied Mathematics. xviii, 528 p. (2003). ZBL1031.65046.