Re: A simple interval challenge
Michel Hack schrieb:
I thought that the different models of IA only differed in the case of
division by intervals containing zero (as endpoint or as interior point).
This is the case for ordinary interval arithmetic.
There are also extensions of interval arithmetic making use of improper
intervals (Kahan, Kaucher, modal arithmetic). They reduce to ordinary
interval arithmetic when applied to ordinary intervals, except in
the case of division by intervals containing zero where there may
again be differences.
Thus, strictly speaking, the standard only needs to address these
issues, and decide about the choices there.
However, to make the best decisions, one needs to know something about
the usage of the arithmetic in particular contexts.
Given an expression, one can simply evaluate it by substituting
intervals. This is called a naive interval evaluation. In many cases
it gives quite poor results.
But there are many ways to massage an expression before or after
applying interval arithmetic, and in the hands of experts
(or software programmed by experts) this enables one to get
better enclosures, and sometimes even the exact range.
Tools such as monotonicity arguments, centered forms, subexpression
analysis, or transformations to equivalent form, more sophisticated
techniques such as Makino's reduction techniques, and even branch
and bound techniques may play a role in such a prior analysis.
This is why interval applications are difficult for non-expert users...
An example how monotonicity analysis improves the quality of bounds is
the linear interpolation expression
f(x,y,t):=(1-t)*x+t*y where t in [0,1].
Given bounds xx on x, yy on y and tt on t (with tt contained in [0,1]),
the naive evaluation is ff = (1-tt)*xx+tt*yy.
For xx=[1,2], yy=[2,3] and tt=[0,1], the range is [1,3] but the naive
evaluation gives ff=[0,1]*[1,2]+[0,1]*[2,3]=[0,5], overestimating the
width by a factor of 2.5.
But it is easy to see that f is increasing in x and y, hence the lower
bound is attained at x=1, y=2, and the upper bound at x=2, y=3.
Thus to get the bounds, it suffices to compute an enclosure for
(1-t)*x+t*y at fixed x,y and interval t, and by rearranging the
expression to x + t(y-x), one gets the exact range of these expressions
by inserting tt in the only occurrence of t.
In the above case, one computes the lower bound from
inf(1+[0,1](2-1))=inf([1,2])=1, and the upper bound from
sup(2+[0,1](3-2))=sup([2,3])=3, confirming that the range is [1,3].
Now in general, one needs of these two enclosures only one bound,
which allows one to save half of the work. The result of our analysis
is therefore an optimal computation without any explicit interval
operation, using (with xx=[xl,xu], yy=[yl,yu], tt=[tl,tu])
set round down
dl = yl-xl;tl1=(tl if dl>=0 else tu);l=xl+tl1*dl;
set round up
du = yu-xu;tu1=(tu if du>=0 else tl);u=xu+tu1*du;
See Section 5.8 of the ViennaProposal-v3.0; I found this special
instance important enough (see the application below to the interval
enclosure of curves) to require its implementation as a special
operation and that of its reverse mode.
In applications of _modal_ interval arithmetic, things are a bit
different. Here one modifies some instance of some variables from
proper to improper by dualizing the interval. (Again, further
massaging may be possible.) Under the right circumstances (a phrase
which needs special attention in each particular case), this
provides still valid and tighter intervals enclosing the range of
the function defined by an expression, and sometimes the exact range,
too.
Clearly, modal intervals can give much better results than naive
interval evaluation; but so do centered forms and monotonicity argument.
For example, xx+tt*(yy-dual(xx)) also provides the exact range in
the above linear interpolation problem, as observed by Nate Hayes,
and put to impressive applications to interval enclosures for
Bezier curves and NURBS (nonuniform rational b-splines).
See his patent
Nathan T. Hayes
System and Method to Compute Narrow Bounds on a Modal Interval
Polynomial Function
http://www.faqs.org/patents/app/20080256155
In the present case, we have two different ways of getting the
optimal enclosure, one without and one with using modal intervals.
The question is therefore one of trade-off between the cost and the
quality of different techniques. For applications involving a huge
number of evaluations of ranges of the same expression (as in
computer graphics), the evaluation must be fast.
The challenge arose from my attempts to find out whether modal intervals
can provide improvements that are difficult to obtain at a similar cost
without using modal intervals, in situations like computer graphics
where speed is a limiting factor.
I am still surprised.
In a week or so, when enough results of the challenge are in,
I'll explain how to use interval arithmetic in an expert fashion
for the challenge example, based on the best techniques supplied
in response to the challenge.
Understanding this may make a significant difference in thinking
about a number of issues in the standard, since high quality software
(and perhaps even optimizing compilers) build upon an implementation
will most likely make use of such techniques.
Arnold Neumaier