Re: YES on Motion P1788/0019.01
Dan Zuras Intervals wrote:
Date: Sun, 12 Sep 2010 21:52:06 +0200
From: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
To: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
CC: stds-1788@xxxxxxxxxxxxxxxxx
Subject: Re: YES on Motion P1788/0019.01
Dan Zuras Intervals wrote:
. . .
We can go as you please but I prefer to consider the
possibility that mid-rad forms have merit.
The merits are such that no one in the last 50 years was moved by
them to create a serious implementation, although the ideas were around
as long as those for infsup.
It is very unwise to cater in a standard for possibilities that
haven't already left a strong trace in the past, and without having
even a blueprint (position paper) on how such a possibility should
be fleshed out.
I am moved by some papers on the subject to consider
that we must find a way to make mid-rads both efficient
& well characterized.
But this is a research project for the future, not a matter for
today's standards committee!
Let those who have the expertise and interest to do so work on
the research project and show that it can succeed.
Let us consider how to standardize their achievements when such a
project has born fruit.
In particular, interval methods have a tendency to turn
floating-point tasks into combinatorial tasks. Thus,
one sometimes has to look at exponentially many endpoints
to find a tightest enclosure.
This is because finding the range of an n-dimensional quadratic
function over a box is already NP-hard.
A midrad arithmetic to be researched cannot change this theoretical
fact, no matter how efficient it is.
The answer to the complexity issue is to use ellipsoids in place
of boxes, not a midrad representation of boxes in place of their infsup
representation. Minimizing a quadratic over an ellipsoid is of
polynomial complexity. Indeed, some people working on the enclosure
of differential equations use this approach. They are not helped
the slightest by the availability of a midrad arithmetic.
But ellipsoids are not very useful in the context of branch-and-bound
methods since splitting ellipsoids does not resuult in ellipsoids.
There are linear algebra problems for which Jacobian
methods exist that circumvent this problem. At least to
a good approximation & only for the mid-rad forms.
No. Please give references if you want to maintain your claim.
If you were thinking of Rump's technique for fast interval matrix
multiplication, you misunderstood their content.
First, his technique has nothing to do with a midrad-only implementation
of intervals, and nothing with a midrad interval arithmetic on single
intervals. They are about midrad matrices only, created on the fly
from the otherwise much more efficient infsup representation, just to
do this particular calculation.
Second, they do not compute the range but only an outer approximation
of the range.
Third, they give _worse_ bounds than the corresponding (still
polynomial) infsup algorithms, by a factor of up to 1.5 in the width.
They are useful _only_ because they give a speedup in a vectorizing
environment. (But not an _exponential_ speedup, as you claim!)
Finally, the standard should provide the basic support, not high-level
features.
But Rump's technique affects only a _single_ high level function
(and perhaps a few more where the same approach can be made to work),
which is as easy to encode in an infsup environment as in a midrad
environment. (And it _is_ encoded only in an infsup environment.)
Thus midrad _arithmetic_ on single intervals contributes not the
slightest to more efficiency.
This means that some problems which are NP-hard for
inf-sup forms are polynomial for mid-rad forms.
No. It is well-known that relaxing the accuracy requirements enough
can turn NP-hard problems into problems of class P.
This has nothing to do with infsup vs. midrad. Indeed, standard
infsup matrix multiplication gives a more accurate polynomial
enclosure than midrad.
It is this that gives merit to mid-rads for me.
In this case, you'd reconsider the facts and then reassess the true
merits.
It is this that makes me believe that we have to find
a way to include them without watering down the
specifications for inf-sup forms.
Well, first show how these contradictory goals can actually be
achieved. Otherwise you only create a dead end thast costs a lot
of people's time without leading anywhere.
It is much better to stay with motion 16 until those who know
this subject far better than you have come up with some convincing
details on how we are to define midrad-only behavior in a way that among
other things, in particular (i) and (ii) are catered for.
If a strong proposal along these lines is made (which I consider very
unlikely), it is still possible to relax Motion 16 at that time.
But it is irrational to do it without having evidence that it would be
an improvement of the standard-to-be.
Arnold Neumaier
Ah, so it is your position that the standard should
eliminate the mid-rad forms altogether in favor of
the inf-sup forms.
No. My position is that the standard should follow Motion 16, which
has a _required_ infsup format, and additional formats (one of which
may be midrad) with a specified conversion behavior.
Then make a motion to that effect. I will second it.
Since I only act as a scientific advisor but am not officially part
of the voting body (I never registered), I do not want to (and cannot)
make any motion. I only help others with making their motions more
precise and useful (as happened in two cases so far, including
Motion 16).
It is a defensible position. It would greatly
simplify our standards work to only have to deal with
the inf-sups from now on. And much that is
controversial about our current approach would have
easy & obvious solutions.
Indeed. But the same holds if one follows the Vienna proposal in these
matters, since there only minimal specifications are required for
additional formats such as midrad arithmetic or Kaucher arithmetic.
But don't go into it thinking that we will not pay
a price for such a simplification. We will.
Therefore the Vienna Proposal did not try to _eliminate_ midrad,
but just made it optional except for conversion tools with a
specified behavior.
This leaves the door open for those who hope to be able to create
a powerful midrad implementation, without forcing the rest of us
to compromise the standard regarding the features that are needed
to be able to work well with intervals containing zero, which are
very poorly handled by midrad.
Arnold Neumaier