2
$\begingroup$

I think the answer is probably no in the linear algebra community, but I'd say anything above $10^8$ and you're starting to lose too much precision, making the situation problematic. In some statistics settings, where they use OLS, I've seen it stated that even values over $20$ are problematic, but that seems pretty extreme. How do you guys assess whether a condition number is "problematic?"

$\endgroup$
8
  • 2
    $\begingroup$ I would consider anything above $1/\sqrt{\epsilon_{\text{mach}}}$ problematic, so it would be floating point system dependent. But it also depends on the size of the linear system. You can create small linear systems (3x3) with a condition number at O(1000) and the solution a computer finds could be out of acceptable tolerance. In general, I tell my students if they are using double precision the danger zone starts at 1000, and they need to be particularly careful if it is above $1/\sqrt{\epsilon_{\text{mach}}}$ $\endgroup$ – Abdullah Ali Sivas May 7 at 13:30
  • $\begingroup$ @AbdullahAliSivas Is it also dependent on what method you're using to solve the linear system? If it's a direct method, I imagine a large condition number is (relatively) less problematic than an iterative method? Also, what is the logic behind $\frac{1}{\sqrt{\epsilon_{mach}}}$. I know what machine epsilon is, but I think I'm having trouble seeing the direct connection. $\endgroup$ – David May 7 at 13:35
  • $\begingroup$ The condition number does not have much to do with stability of the method you are using. For example, say you are using the conjugate gradient method. The error coming from the matrix is at the mat-vec step. So the issue there would be caused by the condition number of the mat-vec operation not the condition number of the matrix. So both a direct method and CG would struggle similarly in that sense. But that doesn't have anything to do with the fact that an ill-conditioned problem is hard to solve independent of however stable the algorithm is. $\endgroup$ – Abdullah Ali Sivas May 7 at 14:08
  • $\begingroup$ $1/\sqrt{\epsilon_{\text{mach}}}$ is some kind of heuristic for me; that is just where I notice things start to break. Like a small perturbation of $\epsilon_{\text{mach}}$ to the matrix (or the right-hand side vector) may cause upto an error of $\sqrt{\epsilon_{\text{mach}}}$ even if you assume that you have a perfect algorithm which does not introduce and propagate errors and is not affected by the floating point arithmetic. And my error tolerance is usually at $10^{-8}$ level which is close to $1/\sqrt{\epsilon_{\text{mach}}}$ in double precision :). $\endgroup$ – Abdullah Ali Sivas May 7 at 14:26
  • 1
    $\begingroup$ @AbdullahAliSivas Why not make all of this into an answer? :-) $\endgroup$ – Wolfgang Bangerth May 7 at 16:10
6
$\begingroup$

This answer is my comments compiled and edited together. I apologize for the repetition.

I would consider anything above $1/\sqrt{\epsilon_{\text{mach}}}$ problematic, so it would be floating point system dependent. But it also depends on the size of the linear system. You can create small linear systems (3x3) with a condition number at O(1000) and the solution a computer finds could be out of acceptable tolerance. In general, I tell my students if they are using double precision the danger zone starts at 1000, and they need to be particularly careful if it is above $1/\sqrt{\epsilon_{\text{mach}}}$.

I want to note that the condition number does not have much to do with stability of the method you are using. Even when it is connected, for example, if you are using the conjugate gradient method, the error coming from the matrix is at the mat-vec step. So the issue there would be caused by the condition number of the mat-vec operation not the condition number of the matrix.

As Federico Poloni pointed out in the comments, the condition number of the matrix-vector multiplication problem is bounded from above by the condition number of the matrix $A$, e.g. $\|A\|\|A^{-1}\|$. However, I think we should rather consider the slightly more general bound for the condition number of mat-vec $Ax$: $\|A\|\|x\|/\|Ax\|$. While we can immediately take the condition number of the problem equal to the condition number of the matrix, I usually see it written as $\alpha\kappa(A)$ with $\alpha=(\|x\|/\|Ax\|)/(\|A^{-1}\|)$. The idea, I believe, is that mat-vec and msolve are inverses of each other, and if one of them is well-conditioned, the other one will be ill-conditioned, similar to multiplication and division (some exceptions apply: $1\times x$ and $x/1$ are both well-conditioned). So, for matrices with high condition number msolves, it still may be the case that $(\|x\|/\|Ax\|)\ll \|A^{-1}\|$. Hence, the condition number of the mat-vec operation may be much lower than the condition number of the matrix. As an extreme example, if $A$ is singular $Ax$ is still meaningful and may be well-conditioned, but $\kappa(A)=\infty$ and $A^{-1}x$ is an ill-posed problem.

So both a direct method and CG would struggle similarly if the elementary steps of the algorithm have issues related to input errors. But this is not the same thing as the conventional wisdom that an ill-conditioned problem is hard to solve independent of how stable the algorithm you employ is.

Note that my arbitrary choice of $1/\sqrt{\epsilon_{\text{mach}}}$ is basically a heuristic for me and, in my experience, it is just where things start to break. As an example, a small perturbation of the relative magnitude $\epsilon_{\text{mach}}$ to the matrix (or the right-hand side vector) may cause up to an error of $\sqrt{\epsilon_{\text{mach}}}$, even if you assume that you have a perfect algorithm which does not introduce and propagate errors and is not affected by the floating point arithmetic. And my error tolerance is usually at $10^{−8}$ level which is close to $\sqrt{\epsilon_{\text{mach}}}$ in double precision :)

$\endgroup$
2
  • $\begingroup$ Thanks for the expanded answer! I still disagree on some points though: (1) if we are speaking about the usual relative condition number, then scalar matrix multiplication and division have both condition number 1, for each $x$. (2) I view matrix multiplication and solving linear systems as perfectly symmetrical operations, when seen as abstract maps: multiplying by $A$ isn't any different than multiplying by $A^{-1}$. The same vector-dependent modification to the condition number can be done for solving linear systems, by multiplying by $\alpha = ||b|| / ||A^{-1}b|| ||A||$. $\endgroup$ – Federico Poloni May 8 at 7:04
  • $\begingroup$ I was thinking more in terms of this answer: math.stackexchange.com/a/3031746 . They are definitely symmetrical when thought as maps, and probably there are matrices for which msolve is well-conditioned but not mat-vec, I just haven't heard of them. $\endgroup$ – Abdullah Ali Sivas May 8 at 7:43

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.