2
$\begingroup$

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?

$\endgroup$
  • 7
    $\begingroup$ 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. $\endgroup$ – Brian Borchers Apr 15 at 15:11
  • 1
    $\begingroup$ 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 $\endgroup$ – Nox Apr 15 at 20:53
  • 4
    $\begingroup$ 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. $\endgroup$ – Wolfgang Bangerth Apr 17 at 3:04
  • $\begingroup$ @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? $\endgroup$ – Mauro Vanzetto May 5 at 17:42
  • 1
    $\begingroup$ @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. $\endgroup$ – Wolfgang Bangerth May 7 at 13:06
3
$\begingroup$

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.

[4] REGULARIZATION TECHNIQUESBASED ON KRYLOV SUBSPACE METHODSFOR ILL-POSED LINEAR SYSTEMS

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.