A simple interval challenge
In discussions with Nate Hayes, he mentioned the following test problem
(arising from a problem in computer vision) as an example for the
potential efficiency of modal interval arithmetic. With his permission,
I make the problem public, adding performance evaluation criteria
for a public contest.
Please send results directly to me at <Arnold.Neumaier@xxxxxxxxxxxx>;
I'll post summaries when something interesting happens.
Arnold Neumaier
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]
The computation together with general theoretical results must
constitute a proof that the result is a rigorously valid enclosure
of the range. (Thus, the relevant cost is that of checking that
some data provided are a certificate for the range enclosure found.)
The operation count (= cost) is in terms of effective interval
operations, defined for simplicity (and in view of potential
hardware realizations) as follows:
- Any unary or binary operation involving an (ordinary or modal)
interval, including taking the hull or the intersection of two
intervals, is counted as an interval operation.
- A purely real operation and a real compare (used in a branching
statement) are counted each as half an interval operation.
- Switches of rounding modes are not counted at present.
A suitable cumulative criterion to be minimized could be
excesscost:=(width/rangewidth-1)^(dof-1)*cost,
where dof=7 is the number of degrees of freedom and rangewidth
(approx. 10.965) is the width of the range (must perhaps be computed
to higher accuracy). This formula comes from the asymptotic
behavior of a very simple branch and bound scheme using simple
interval evaluation.
I think this is an ideal test problem for good students - please try
it out!
I'd be interested in being informed (preferably until December 3, 2008)
of resulting bounds and operation counts, together with an indication
of the techniques used, and/or a complete algorithm realizing the
enclosure (preferably in Intlab). For the sake of simplicity, you may
at present ignore rounding error issues.
Background information:
----------------------
The range to 4 significant digits is [-2.956,8.009].
Simple interval evaluation gives the poor enclosure [-7.4889,19.2889]
(244% of optimal width) with 21 interval operations, using savings
due to precomputing u = w^2+x^2 and v = y^2+z^2 and evaluating
f = (a*(u-v)+2*(b*(x*y-w*z)+c*(x*z+w*y)))/(u+v).
(excesscost = 1.89e+2)
Nate Hayes has a confidential algorithm which computes
the bounds [-3.2555,9.1556] (113% of optimal width) with 67.5
effective interval operations, using modal intervals.
(excesscost = 3.55e-4)
I get the slightly inferior bounds [-3.2697,9.2222] (114% of
optimal width) with 62 effective interval operations, using
monotonicity arguments and term rearrangements.
(excesscost = 4.49e-4)
Can anyone do significantly better, either in terms of speed
(then with comparable accuracy), or in terms of accuracy (then
with comparable speed), or in terms of excesscost?