3
$\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?

Improve this question
$\endgroup$
8
  • 9
    $\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, 2019 at 15:11
  • 2
    $\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, 2019 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, 2019 at 3:04
  • 1
    $\begingroup$ @WolfgangBangerth I think this is a little bit pessimist view, i.e. with preconditioning same cases, not all, can be manage without change the math problem. Am I too optimistic? $\endgroup$
    – Mauro Vanzetto
    May 5, 2019 at 17:47
  • 2
    $\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, 2019 at 13:06

1 Answer 1

Reset to default
2
$\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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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