Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It is hoped that in the future with the advent of quantum computing that fundamental operations on a computer will have arbitrarily high precision. Moreover, that even with such high precision, computation times with be realistic. An important concept in Numerical Analysis is ill-conditioning.

For instance it is common to call the following problem, an ill-conditioned problem:

Finding the roots of a quadratic polynomial. The example is from Datta, BN Numerical Linear Algebra and Applications SIAM, Second edition (2010)

$ z^2-2z+1=0 \rightarrow z^2-2.0001z+1=0 $

since a relatively small change in the polynomial coefficients can cause a much larger perturbation in the polynomial roots.

However the ill-conditioning doesn't seem to be part of the problem because in arbitrarily high precision we have the quadratic formula allowing us to compute the roots. The ill-conditioning seems to be caused by working in finite precision which is not inherent to the problem.

Researchers often talk about the difference between an ill-conditioned problem and an ill-conditioned method of solving. This distinction seems to be entirely blurred to me.

To help clarify the situation I have two closely related questions:

  1. Is ill-conditioning an issue in arbitrarily high precision?

  2. Is there an ill-conditioned problem which remains ill-conditioned even in infinite precision computing?

share|improve this question
4  
Is the connection between quantum computing and arbitrarily high precision operations obvious? –  j.c. Jun 1 '11 at 19:17
1  
Regarding your example, the first polynomial has a double root. This means that its coefficients lie on a very special lower dimensional set given by the vanishing of the discriminant. So in this case the problem is ill-conditioned because arbitrarily tiny perturbations exist that will take you off this set and change the character of the solution. So I don't see how any assumed level of precision enters the definition of ill-conditioning given for instance in en.wikipedia.org/wiki/Condition_number –  j.c. Jun 1 '11 at 19:25
    
However, the problem of finding the roots of $z^2-2z+1=0$ can be computed exactly on a computer because the numbers $1$ and $2$ have exact representations as floating point numbers. Are there severely ill-conditioned problems which cause no concern when computing in finite precision? –  alext87 Jun 2 '11 at 6:48
2  
I don't believe in your first paragraph about quantum computing. –  Zsbán Ambrus Jul 3 '11 at 12:49
add comment

3 Answers

up vote 15 down vote accepted

Ill-conditioning isn't a concept that depends on the precision that you use to compute the solution. "A small change in the data turns into a large change of the solution" isn't a concept that involves actual computation. Think of it as "the map data $\mapsto$ solution has a large Lipschitz constant".

The error on the input data does not come only from finite precision representation: most data you put into a computer come from physical measurements or approximation processes, and often the error implied by these measurement/processes is way larger than one part in $10^{-16}$. How many physical constants do we know up to that precision, for instance? Ill-conditioning says that you need to provide your input data with a large precision, otherwise any solution you get will be rubbish, even in infinite precision arithmetic.

Ill-conditioning per se refers only on the sensitivity to input data and is independent of the actual method you use to compute a solution. The error introduced by using finite precision along the computation (highly depending on the algorithm, including order of summation and parenthesization) is often referred to as algorithmic error or stability of the algorithm.

share|improve this answer
3  
Federico's answer is good. I would just like to add that if a problem is ill-conditioned (in infinite precision arithmetic), then necessarily it will be algorithmically unstable (in finite precision arithmetic). The reason is that the initial data will need to be rounded to the nearest floating-point-representable number. Even if the algorithm commits no further errors, it will still have large error because of this initial rounding error. –  David Harris Jun 1 '11 at 20:10
    
To support the point "arithmetic precision is not so much relevant with respect to errors in the data", I can add that in the last 20 years the precision used in scientific computation hasn't increased, despite the huge advances in computational power. In fact in some cases it has decreased, since GPU architectures often support only single precision. So, while 640k are not enough for anybody, apparently 16 digits are. –  Federico Poloni Jun 1 '11 at 21:10
1  
@Federico: GPU's are designed for graphics (i.e. games), not scientific computing. GPU manufacturers typically add double-precision support specifically to accommodate scientific computing. Current or forthcoming x86 chips will have extension for quad-precision. (And of course there are multiprecision libraries). –  David Harris Jun 1 '11 at 21:41
add comment

It's worth pointing out that many inverse problems in the functional analytic setting go beyond ill-conditioning to ill-posedness. That is, a small change in the data (noise) can lead to an aribtrarily large change in the solution to the inverse problem.

In finite dimensions a linear system can be well or ill conditioned, but if the system isn't singular, then there will be a bound (the condition number) on how badly noise in the right hand side of the system of equations can grow in the solution. In the infinite dimensional setting there isn't necessarily even such a bound.

share|improve this answer
add comment

This was meant to be a comment on Federico Poloni's answer, but I don't see any add-comment button.

Consider the two standard statistical calculations, sum and sum-of-squared-deviations:

$s(x) = \sum_{i=1}^nx_i,\ $ and $\ \ d(x) = \sum_{i=1}^n(x_i-s(x)/n)^2.$

The 2-norm condition numbers of these mappings are

$\kappa_2(s(x)) = \sqrt{n\frac{\sum x_i^2}{|\sum x_i|^2} },\ \ $ and $\ \ \kappa_2(d(x)) = \sqrt{\frac{\sum x_i^2}{d(x)}}$

If $x = (m,m+1,m+2)$, then $s(x) = 3m+3$, and $d(x) = 2$, and we have:

$\kappa_2(s(x)) \approx 1$, and $\kappa_2(d(x)) \approx m$, for large $m$.

This means that $s(x)$ is well-conditioned for this data, while $d(x)$ is ill-conditioned for the same data.

It is important to realize that it is the problem and its input data that are well- or ill-conditioned and not just the data.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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