On Arnold's challenge & Paul's Observation...
> Date: Thu, 27 Nov 2008 10:16:38 +0100
> From: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
> To: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
> CC: interval <reliable_computing@xxxxxxxxxxxxxxxxxxxxxx>,
> 1788 <stds-1788@xxxxxxxxxxxxxxxxx>
> Subject: Re: A simple interval challenge
>
> First intermediate report (Nov. 27, 2008)
>
>
> > Challenge:
> > ---------
> > Find a cheap and good enclosure for
> >
> > f := (a(w^2+x^2-y^2-z^2)+2b(xy-wz)+2c(xz+wy))/(w^2+x^2+y^2+z^2)
> >
> > given the following bounds on the variables a,b,c,w,x,y,z:
> >
> > a in [7,9]
> > b in [-1,1]
> > c in [-1,1]
> > w in [-0.9,-0.6]
> > x in [-0.1,0.2]
> > y in [0.3,0.7]
> > z in [-0.2,0.1]
>
> [...]
>
> > . . .
>
> Mihaly Markot calculated the global extrema to high accuracy.
> The global minimum -2.95607850118520?9 is attained at
> (a,b,c)=(9,1,1), (w,x,y,z)=(-0.6,-0.04181974?8,0.7,-0.2).
> The global maximum 8.00936984210601?8 is attained at
> (a,b,c)=(9,1,-1), (w,x,y,z)=(-0.9,0.2,0.3,0.04115383?9).
> Thus the width of the range is 10.9654483432912?2
> Here the number s after the ? denotes an uncertainty of s units
> in the last place.
>
> . . .
>
> Arnold Neumaier
Folks,
On this last bit, from sage:
At (a,b,c) = (9,1,1), (w,y,z) = (-3/5,7/10,-1/5),
the minimum of f
fmin = (270 - sqrt(284186))/89 =
-2.95607850118512578703579097311594569123011562791870384959664839896...
is attained at
x = (531 - sqrt(284186))/50 =
-0.04181973210952390092370793214638333038960581769529285228203415016...
At (a,b,c) = (9,1,-1), (w,x,y) = (-9/10,1/5,3/10),
the maximum of f
fmax = (7*sqrt(13090) - 48)/94 =
8.009369842105960925002100756373148691442795394242483054310624547464...
is attained at
z = (sqrt(13090) - 114)/10 =
0.041153787970861813574249587129656814223182386554191530074267249452...
resulting in a width of
fmax - fmin = (94*sqrt(284186) + 623*sqrt(13090) - 29652)/8366 =
sqrt(284186)/89 + 7*sqrt(13090)/94 - 14826/4183 =
10.96544834329108671203789172948909438267291102216118690390727294643...
But, I don't think this is (or should be) the point.
This example demonstrates several things to me.
(1) A blind translation of a real expression to an interval
evaluation may report intervals wider than can actually be
attained.
(2) There are some re-arrangements (dare I say, optimizations)
that a compiler might do that would help matters (e.g.,
evaluating a given interval only once in a formula in which
it appears more than once).
(3) There are other, perhaps more powerful re-arrangements
(mostly algebraic in nature) that help even more but should
be forbidden to compilers on the grounds that they change
the calculation. These appear to be equivalent to the so-
called 'value changing optimizations' in 754.
Point (1) may forever be a limitation of intervals as a
concept.
Arnold, this example is complex enough to demonstrate your
point but I would like to see a list of simpler examples of
things in point (2), say replacing x*x with x^2, that you
think should be permitted (or mandated) in the evaluation
of interval expressions.
Then, those things in point (3), say replacing an expression
like (x^2 - y^2)/x^2 with 1 - (y/x)^2, should also be listed
but, as they are value changing, reserved to the programmer
to use or not, as the problem warrents.
Finally, Paul Zimmermann made an interesting observation the
other day:
> From: Paul Zimmermann <Paul.Zimmermann@xxxxxxxx>
> To: Ulrich Kulisch <Ulrich.Kulisch@xxxxxxxxxxx>
> CC: gdr@xxxxxxxxxxxxxxxxxxxxxxxx, george.corliss@xxxxxxxxxxxxx,
> stds-1788@xxxxxxxx
> Subject: Re: Balance
> Date: Tue, 25 Nov 2008 15:35:49 +0100
>
> > On all existing processors interval operations are slower by magnitudes
> > than the corresponding floating-point operations. This is the great
> > hindrance to a wider acceptance. The main reasons why software
> > simulations of interval arithmetic are slow are the case selections for
> > interval multiplication (9 cases) and for division (14 cases) and the
> > simulation and frequent changes of the rounding mode.
>
> in a Dagstuhl seminar in January 2006, Branimir Lambov showed how to use
> *existing* hardware (namely SSE-2) to get fast interval arithmetic. See
> kathrin.dagstuhl.de/files/Materials/06/06021/06021.LambovBranimir.Slides.pdf,
> especially slide 18. Does any current implementation make use of his ideas?
>
> Paul Zimmermann
I was unaware of this work which implements an interval
as an ordered pair of floats, (lower,-upper), in which
all arithmetic is done in round-to-minus-infinity.
This is a remarkable result in that it allows fast &
efficient intervals to be implemented in parallel hardware
that exists today without all the rounding mode changes
that get others into so much trouble.
This suggests to me that we may as well go ahead & define
an interval inter = (lower,upper) as conceptually (or
semantically) consisting of its lower & upper bounds with
operations performed in the direction of those bounds.
But we should NOT require that the memory encoding appear
that way. (In fact, we should point out Lambov's approach
as a practical example of another way.)
The most we should say is that there exists a constructor
interval(lower,upper) & extractors lowerbound(inter) &
upperbound(inter) that operate without floating-point
errors of any kind including inexact.
This would permit Lambov's method as part of a conforming
implementation as well as others we may not have thought
of yet.
You know, this hardware thing may not be as difficult as
we thought.
Enjoy,
Dan
P.S. - BTW, this approach also excludes things like the
(center,radius) form for which others have described both
conceptual & practical difficulties. We can still have
extractors of the form center(i) & radius(i) for which i
is contained in (center(i)-radius(i),center(i)+radius(i))
but we need not demand that they be error free.