(j3.2006) Liaison to IFIP WG 2.5

[Van Snyder]

On Tue, 2007-08-21 at 19:44 +0100, Lawrie Schonfelder wrote:
> I do not see the need for intervals generally. There may be some
> critical steps in some very specialist applications where it becomes
> essential that the true result is bracketed but most of the time a
> well constructed FP calculation will do just fine.

An important example, but not the only one, is Newton iteration.  In
point arithmetic, even with unlimited but finite precision, it can be
shown that a Newton iteration in the complex plane for something even as
simple as square root is chaotic for some arguments and starting values,
i.e., it doesn't converge in a finite number of iterations.  However, a
Newton method implemented properly in interval arithmetic converges
globally and quadratically.

Another important example is minimization.  In point arithmetic, global
minimization is exceedingly difficult.  In interval arithmetic, it's
pretty straight-forward.

Another important example is quadrature.  In point arithmetic, it's easy
to construct examples where any code will under-estimate the error,
sometimes by a significant amount.  Here's how to fool it:  Pick a
random function and integrate it.  Keep track of the abscissae it uses.
Then integrate the square of a polynomial whose zeros are at those
abscissae.  The code will estimate the answer is zero with very small
error, while it's clearly not zero.  Quadrature implemented carefully
using interval arithmetic doesn't have this disease.

The list goes on....  Just about any problem involving calculus or
nonlinearity benefits from interval computations, and linear algebra and
FFT (where most of the cycles in engineering and scientific calculations
go) benefit from it too.

> Provided the system and the hardware supports the necessary directed
> roundings existing Fortran can, via modules, support adequate interval
> arithmetic operations. Doing whole applications in intervals probably
> indicates an inadequately analysed problem.

Simply providing directed roundings and ways to select them isn't
enough.

Modules are actually not an adequate foundation for serious interval
computations, given the way Fortran provides support for directed
roundings.  The problem is compounded by the way Intel provides support
for directed roundings: changing the rounding mode flushes the pipeline
and waits to dispatch the next FP instruction until it's empty.  Between
the overhead of specifying the rounding mode, and the behavior of the FP
unit, 100X overhead compared to point arithmetic is not uncommon and not
unexpected.

I don't think anybody would do a whole application in characters or bits
or derived types or co-arrays, either, although I have seen entire
applications, of goodly size, in integers (and Hollerith;-).

The history of mathematical software is the provision of carefully
written computational kernels for narrowly-specified mathematical
operations (such as FFT or zero finding).  These, and the user-provided
code they frequently need, not entire applications, are where interval
arithmetic would be used.

-- 
Van Snyder                    |  What fraction of Americans believe 
Van.Snyder at jpl.nasa.gov       |  Wrestling is real and NASA is fake?
Any alleged opinions are my own and have not been approved or
disapproved by JPL, CalTech, NASA, the President, or anybody else.