"Grand Challenge" Interval Problems (by A. Neumaier)

Date: Wed, 17 Apr 2002 22:10:51 +0200
From: Arnold Neumaier 
To: interval 
Subject: "grand challenge" interval problems

What are the "grand challenge" interval problems? 
I see several challenges:

1. Large-scale global optimization. Although this is NP-hard, so is
mixed integer programming; nevertheless large mixed integer programs
are solved routinely (though not all of them). Global optimization is 
the only area of wide practical applicability where intervals are 
likely to have a major impact in the near future.

2. Error bounds for realistic discrete finite element problems 
with realistic (dependent) uncertainties. Applications abound, and
interval 
methods could become competitive, as replacement for Monte-Carlo 
studies. (See recent discussions on this list with Pownuk and Muhanna.)

3. Solution of large and sparse linear equations with interval
coefficients. Apart from a paper by Rump, nothing has been done,
although sparse matrices are ubiquitous in applications.

4. Error bounds for large systems of ODEs. Both AWA and COSY 
which were recently under discussion, only handle very small 
systems; already modeling the sun and planets (without asteroids) 
over 10 years is probably too hard for present codes. 
(But the goal should be to produce verified ephemerides...)

5. Error bounds for stiff sytems and singularly perturbed systems of 
ODEs. The books by Hairer and Wanner contain enough analytic results 
that could be used to get a start, by creating variants of the results 
with constructively verifiable assumptions.

6. Error bounds for elliptic partial differential equations on 
irregular meshes. Most applications have their mesh adapted to the
problem; current interval work is mostly on toy problems with very 
simple domains. Some applications are in the inverse monotone regime,
(so that a solution of problem 3 is not needed for these problems).

I do not know whether most everyone could agree on these 
(given that there is not even agreement on empty intervals and NaNs).

But I have good reasons to think that each of these problems is of
high significance, nontrivial, and tractable if it is made the focus 
of a group of good and dedicated mathematicians. Apart perhaps 
from 3., it requires the dedicated collaboration of several people 
to get the work done at a sufficiently high quality level.
(If I could multiply myself by 12, I'd set two copies each of myself 
working on each topic. As it is now, I divide myself between the 
six topics and numerous non-interval ones, and achieve nothing; 
at least, I make some effort to concentrate on topic 1.)

In each case, success would be measured by the availablility of an
easy to use software system, perhaps based on Intlab, that can be 
given to people working in applications to check it out. 
(As in the past, without that, interval techniques are doomed to a 
fringe existence.) It need not compete in speed with nonrigorous 
software, but it must provide realistic bounds for realistic-sized 
problems. 

And all problems require a solid understanding of the corresponding
techniques from the analytical side, since they are not simply 
solvable by applying interval recipes to a problem, but only by 
translating the theorems and techniques of the application into
sharper versions that allow one to add quantitative aspects to
previously qualitative or asymptotic reasoning, and analytic rigor to 
previously approximate computations. 

Interval analysis is nothing else than mathematical analysis (and
linear algebra) on the computer. To think of it as a separate 
discipline is a mistake, and progress in interval analysis is
always based on better understanding of the relevant mathematical 
analysis in the various applications. What is special about interval
analysis is only the perspective.

Best wishes,

Arnold Neumaier

P.S. A more detailed manuscript can be found at the following
webpage

Back to Open Problems of Interval Computations

Back to the main menu of the Interval Computations website