Re: Definition of intervals as subsets of R - the bad news
Dear all,
interval arithmetic deals with closed and connected sets of real numbers
(and nothing else).
The just approved IntervalStandardNotation specifies two sets of
intervals: IR and *IR. IR is the set of nonempty closed and bounded
intervals over R and *IR is the same as IR* would be.
Regrettably the set that should be the base for an interval arithmetic
standard is not mentioned is the IntervalStandardNotation. In the paper
I prepared for the procedeedings of the Dagstuhl meeting (2008) I used
the notation (IR) for this set. It denotes the set of closed (bounded
and unbounded) real intervals. The difference between IR* and (IR) seems
to be marginally but it is essential!
Arithmetic for real numbers and for sets of real numbers is well
defined. For elements of (IR) formulas for the arithmetic operations can
be derived from the definition of the operations for sets of real
numbers in a strict mathematical manner. The calculus {(IR), +, -,*, /}
is free of exceptions. Of course, operations can also be defined between
an interval of (IR) and a real number. In such expressions a real number
x is regarded as the interval [x,x]. A real number or an interval over
the real numbers is mapped onto the smallest floating-point interval
that contains the number or interval respectively. So in double
precision floating-point arithmetic the image of the real number 10^500,
for instance, would be the interval [maxreal, +oo). A floating-point
computation may deliver results like +oo, -oo, or NaN which are not real
numbers. If they are to be mapped on an interval their image can only be
the empty set.
A consequence of an interval arithmetic standard must and will be that
interval arithmetic is supported by the computer's hardware. This
requirement is as old as interval arithmetic itself. It can already be
found in Sunaga's early paper. In hardware an interval operation is
about as fast as a simple floating-point operation. Then it is no longer
necessary to develop routines for operations between an interval and a
real number for reasons of speed. Hardware support for interval
arithmetic (and of an exact dot product) would dramatically change the
world of computing. The simpler an interval arithmetic standard is going
to be the sooner we will get it hardware supported. In simplicity lies
truth.
With best regards
Ulrich Kulisch
Siegfried M. Rump schrieb:
> Dear all,
>
> now I found time to work on the change of INTLAB according to the
> anticipated new definition of intervals as subsets of R. However,
> a number of problems occur.
>
> Theoretically, we have the simple formula
>
> [ainf,asup] + [binf,bsup] = [ainf+binf,asup+bsup] .
>
> In practice, I distinguish various cases such as
>
> IR op R
> R op IR
> IR op IR .
>
> Now [ainf,asup]+inf may occur, and I have to check whether
> ainf=-inf. You can imagine that many case distinctions are
> necessary. Moreover, I often optimize the code when one
> operand is scalar, not to speak of complex intervals, which
> are treated in INTLAB as well. Really awkward becomes the
> multiplication of two matrices where some of the n^3 products
> may be 0*inf or inf-inf may occur.
>
> The case distinctions are all done for the sake of speed.
> If only scalar intervals were involved, this may not be
> beneficial. However, INTLAB is the toolbox for verified
> computations in Matlab, and as the name says, this is a
> Matrix Laboratory.
>
> In a nutshell, defining interval to consist only of finite
> numbers is a nice concept, but various exceptional operations
> such as 0*inf or inf-inf have to be identified and redefined.
> For example, this slows down addition by about a factor 2.
> I am afraid, a penalty might also apply to a C- or Fortran
> implementation.
>
> At least for my INTLAB this is hardly acceptable. The difference
> between the current state and the anticipated change is only
> the handling of infinity. In many applications infinity hardly
> occurs, so all computations are slowed down for not much benefit.
>
> I want to stress again that these are my implications for INTLAB,
> forcing me not to do the intended change. From a mathematical
> point of view I am much in favor of intervals being sets of
> finite numbers; just 0*A for any interval A is such a nice
> property.
>
> However, for the time being interval arithmetic depends on the
> IEEE 754 floating-point standard. Hence special care is necessary
> for exceptional operations such as 0*inf or inf-inf.
>
> Best wishes
>
> Siegfried M. Rump
>
>