Date: Wed, 17 Apr 2002 22:10:51 +0200 From: Arnold NeumaierTo: 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