Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Please listen to Ulrich here...

Dear Ulrich,
Thanks for responding and for most, but not all your efforts to promote computing with intervals.
Not all interval computations in which inputs are non-degenerate intervals are NP-hard. Moreover, just because a problem is NP-hard does not meant there are situations in which such problems can be solved using interval arithmetic when inputs are not degenerate intervals.
Virtually all real engineering problems have measured inputs, the interval bounds to which must be non-degenerate. A good example is the one you yourself have used in which you computed the resonating spin rates of a steam turbine as the roots of a nonlinear equation. The problem is that although numbers used to describe the physical characteristics of the turbine were only reported to 4 or 5 digits, you assumed they were infinitely accurate degenerate intervals. I believe this to be a mistake and resulted in misleading conclusions from your computations using CA and EDP.
Had you used appropriately wide interval bounds on the measured inputs, the apparent usefulness of CA and EDP would have vanished.
I have no quarrel with using CA and EDP to bound rounding errors when computing solutions to mathematical problems in which all inputs are infinitely precise. My quarrel is with incorrectly assuming measured input values, including bounds on physical constants like those available from NIST, are infinitely precise degenerate intervals.
So, in the references you cite below, are inputs degenerate intervals, or not? If they are not, and if CA and EDP substantially reduced the width of computed interval bounds, then they are counter-examples to what I believe to be true and I will stop commenting on this issue. If inputs are degenerate, these references do not disprove my thesis.
Finally, my concern has implications for any proposed interval standard. As we did at Sun, I believe that default I/O conventions should be that when a small number of digits are input to an interval, no more accuracy should be assumed than is actually supplied by input digits. Therefore, 0.100 should be interpreted either as [0.099, 0.101] or [0.995, 0.1005]. Interval I/O should require extra effort to input the number 0.1 as a degenerate interval, for example, by requiring [0.1], [0.1, 0.1], or 0.1000000000000000000000... 
to be input.
Otherwise more people will be mislead into making the same kinds of mistakes you appear to have made in the past. 

Best regards,

Bill


On 8/19/13 9:51 PM, Ulrich Kulisch wrote:

Dear Bill,
it may well be that CA and the EDP are not well suited for solving problems which in general are NP-hard.
The usefulness and necessity of CA and the EDP for other problems, however, have repeatedly been shown in the literature. As examples I just refer here to three articles in the volume: U. Kulisch and H. J. Stetter: Scientific Computation with Automatic Result Verification, Computing Supplementum 6, Springer 1988. [1] Th. Ottmann, G. Thiemt, Ch. Ullrich: On Arithmetical Problems of Geometric Algorithms in the Plane. 
[2] R. Lohner: Precise Evaluation of Polymomials in Several Variables.
[3] H. C. Fischer, G. Schumacher, R. Haggenmueller: Evaluation of Arithmetic Expressions with Guaranteed High Accuracy.
CA and the EDP can, for instance, also be very useful for so called "Numerical Verification Methods" or "Computer-Assistsed Proofs". Such methods do not just compute bounds for the error of an approximate solution but also prove the existence of an exact solution within the computed bounds. Examples are: a partial differential equation or a system of linear or non linear equations. 

With best regards
Ulrich



Am 08.08.2013 19:09, schrieb G. William (Bill) Walster:

Not seeing a post with an example, may I conclude that there are none?

Cheers,

Bill


On 8/7/13 9:03 AM, G. William (Bill) Walster wrote:



Please provide one example of how an exact EDP can substantially
reduce the computed width of *any* interval computation in which none
of the inputs are degenerate intervals and therefore infinitely precise. 

Thanks in advance,

Bill

On 8/7/13 2:24 AM, Dan Zuras Intervals wrote:

     Folks,
When Ulrich talks about problems with exact dot product he has some 
     experience in the matter.  More than the rest of us put together.
     If we are about to have a standard that admits the possibility of
a member that CANNOT do an exact EDP, all our work will be wasted. Please consider rewording this document in Ulrich's favor this time. He is not just blowing smoke. It is hard but it is necessary. Or, 
     at least if we make it so.

     Let's make it so.

     Yours,

                     Dan