Applications of intervals

[George Corliss]

Phuong Vu asked

> I am being asked a question about the need for having
> interval/multiple precision arithmetic to be implemented
> on supercomputers.  I know you have done a lot of work in this
> area and perhaps you could shed some light on the need to have
> interval arithmetic (regardless of the cost of implementation).
> I am looking for some REAL example which shows that you can 
> do without interval arithmetic or that you cannot live without it.

I have delayed a bit in replying because a full reply should fill a
book.  Literally.  You ask a tough question to which I will attempt
an outline of an answer.

Disclaimer:  The interval croud has historically tended to oversell
its wares (as many areas of research do).  We have gotten a bad
name for that.  I attempt to be objective, but I DO have a bias.
Also, other interval workers have different opinions from mine.

There seem to be emerging three areas in which interval
computations can do science that approximate methods cannot
   1.  Global optimization
   2.  Automatic result validation
   3.  Study of uncertain parameters


1.  Global optimization
    Conventional algorithms have become quite robust, but they can
still be fooled, and they may require lots of time for some classes
of practical problems.  Jansson (Hamburg) has reported solving a
large suite of global optimization problems competatively with his
interval algorithm compared with competing standard methods.  The
reason is that interval methods are able to through away large
regions of the box in which they can guarantee that no global
optimum exists.  It is easy to find an interval bound for the range
of a function in a box.  The bounds are often not tight, but if the
lower bound > f* = upper bound for the global min, then the box can
be thrown away.  Guaranteed.  Similarly, if f' is bounded away from 
zero, the box can be discarded.  The result is that large regions are
discarded rapidly.

Eldon Hansen, Global optimization Using Interval Methods, Dekker,
1992, is a good reference.

At a recent meeting in Lafayette, we heard talks by a robotics
person who had used interval optimization to solve a problem in
computer vision.  He was doing parameter identification.  The
needed resolution was very course most of the time, and his
interval algorithm was faster because it knew when it could safely
ignor regions, even at course tolerances.  A physisict on the SCSC
project discussed interval optimization techniques in the context
of the beam stability problem.  A mathematician working with Boeing
discussed an interval solution to a materials design problem.

Many workers with conventional algorithms are not yet convinced of 
the merits of interval optimization techniques.  One issue is problem 
size.  Jansson and Hansen have each handled problems with several hundred
variables, but they have not yet attempted problems of the scale
approximate methods handle routinely.  I do not know exactly what the 
limits are for the interval techniques, but one of the limits has been
a limited number of researchers in the area.  In the limit, interval
techniques can probably handle very large problems, but
conventional techniques may always be able to handle larger ones.

2.  Automatic result validation
    In some applications, one seeks assurances that you have
computed the correct answer, and a speed penalty of 2 - 10 is an
acceptable price to pay.  Several researchers have looked at
dynamical systems, eg. Adams, Lohner, Ely, Rufeger, Kuhn, Ames, Corless
(not me, but Rob at U of Western Ontario).  They consider problems
for which conventional methods, even with very high multiple
precision computations, have not been able to distinguish true
mathematical chaos from chaos caused only by the numerical method.
By computing intervals in which the true answer is guaranteed to
lie, there can be no question of what is actually computed.

Adams showed previously unknown regions of instabilities in tests 
for large industrial gears and turbines.  That is important because
a 20 ton gear gets very exciting when it excites an unbounded
oscilation!  Adams and his students have also validated the
existence of periodic solutions in nonlinear chemical reactions and
studied the sources of chaotic behavior in orbits of satelites and
in the Lorenz equation.

I worked with mathematicians at Amoco to use interval techniques to
discover sources of instability in a small portion of a resevoir
simulation model.  We used intervals to locate the trouble.  Then
they worked around the difficulty using conventional methods.  The
interval methods gave insight, but the production code continued to
use standard methods.


3.  Study of uncertain parameters
   In many applications, we work with uncertain data.  We can build
our models using interval-valued parameters.  Interval computations
are then worst-case computations.  Sometimes that is what is
needed, and sometimes bounds computed that way are overly
pessemistic.  The speed of interval computations is often orders of
magnitude faster than hundreds or thousands of simulation runs.


A book edited by Kulisch and Adams has recently appeared, 2/3 of
which are industrial applications of interval techniques.

George F. Corliss
georgecaboris.mscs.mu.edu