Arguments for supporting Motion P1788/0023.01:NoMidRad
Ralph Baker Kearfott wrote:
The motion has been put forward by Arnold Neumaier (through Dan Zuras),
I didn't forward the motion. I only suggested a wording for this motion,
which was put forward by Dan Zuras.
and has
been seconded by Nate Hayes. The discussion period therefore begins,
and will
continue until after the end of Tuesday, October 5.
Juergen: Please post this information on the web page.
William: Please record this in the minutes.
The motion is as follows:
----------------------------------------------------
The standard shall not support a midrad interval format or
nonstandard intervals, beyond providing conversion support,
approximately to the extent specified in the Vienna Proposal.
----------------------------------------------------
P.S. As I expressed earlier, I think "support" needs to be
clarified. Also, isn't saying that the standard shall
not support non-standard intervals a tautology?
As just said in another mail:
The motion is constructive only if ''supported'' is meant in the sense
formally introduced in Motion 16.
Thus, apart from conversion issues, specifications shall be provided
by the standard only for inf-sup interval types, and only for
standard intervals, i.e., those that represent closed and connected
sets.
On the other hand, nothing should prevent implementors from providing
arbitrary functionality for midrad interval or nonstandard intervals,
as long as the required conversion rules to all (and at least one)
supported infsup datatype are respected.
The arguments for the motion are repeated below.
Arnold Neumaier
=========================================================================
1. General arguments
1.1. This keeps the standard simple in language and requirements,
and makes it easy to comprehend. Adding midrad interval or nonstandard
interval support makes the standard much more complex. Leaving it out
frees both the standardizing committee and implementors of the
standard from unnecessary work.
1.2. This standardizes just the parts that are widely used in practice,
and for which half a century of experience is available.
1.3. It suffices for virtually all applications, and there are only
very special cases where it might not be the most efficient solution.
1.4. No strong case has been made that midrad or nonstandard arithmetic
is actually more efficient on a significant class of problems than what
can be done without it.
1.5. For applications only involving those operations where
tightest results are required, it ensures full reproducibility of
the results.
1.6. Standard interval arithmetic can be strongly constrained in an
easily specifiable and easily understandable way, and it is known how to
enforce these constraints efficiently. (In contrast, midrad interval
arithmetic and nonstanderd interval arithmetic exist in multiple,
mutually inconsistent variants, none of which can clearly be
distinguished as superior.)
1.7. By being silent about implementations of unsupported but available
interval datatypes (in the sense of Motion 16), it leaves those who
want to write experimental implementations with these datatypes
complete freedom to explore the possibilities, so that there is no
barrier for potential developments of these techniques.
The availability of conversion requirements gives these developments
a minimal support.
2. Why no midrad support?
This was not argued in the context of the Vienna Proposal, since at
that time I couldn't imagine that anyone would seriously want to have
a midrad implementation. But midrad (and especially a midrad-only
implementation) cannot serve as a useful standard for many reasons.
2.1. Lack of experience and research to support a standardization
2.1.1. A standard should cater for a large group of users.
Almost nobody uses midrad arithmetic for single intervals,
and nobody uses a midrad-only arithmetic. (The only significant use
is to vectorize matrix multiplication in IntLab, which is done in an
infsup environment by converting on the fly in vector mode to midrad
and back, gaining a factor of O(m) in speed, where m is the
vectorization size, but at the cost of losing up to 50% in the
resulting width.)
2.1.2. Most literature on midrad arithmetic is purely theoretical,
assumes exact arithmetic, and is concerned with the four binary
operations + - * / only.
2.1.3. No implementation exists that has correct outward rounding and
more than the four binary operations + - * /. Implementations of the
latter are not widely used either.
2.1.4. Almost no studies exist on how rounding errors are correctly
handled in midrad arithmetic. For elementary functions, the only
straightforward way is to proceed by conversion to infsup and back.
This makes midrad elementary functions slow and shows that midrad
is not a natural independent datatype.
2.1.5. The case for an efficient implementation of single operations
that can compete in speed with infsup and correctly accounts for
rounding errors has not even been made for the four elementary
operations -- neither in theory nor in practice. There is neither
a trial implementation nor a theoretical paper discussing the
relevant issues.
2.1.6. Almost 50 years of interval computing that have not produced
a single outward rounding midrad implementation including some of
the standard functions would be reason enough not to create a standard
that allows it while not providing what already proved useful and
tested.
2.1.7. Two years of discussion of the standard didn't produce a single
position paper on the matter that addresses this sort of questions,
let alone a public pilot implementation of the elementary functions
that would show which requirements on a midrad implementation beyond
simple valid enclosure can be imposed meaningfully.
2.1.8. Because of 2.1.1-7, including midrad into the standard is
premature and prone to make poor choices.
2.2. Lack of support for handling wide intervals
2.2.1. Midrad cannot support half-infinite intervals such as [0,inf],
very important for global optimization.
2.2.2. For bounded intervals such as [1,u] with u around 1e17,
not even the correct sign is guaranteed when the midpoint and radius
are IEEE doubles, and the same happens already for small u when the
radius is restricted to fit into one or a few bytes.
2.2.3. It is easy to simulate midrad arithmetic in terms of infsup,
while the converse is impossible because of the limitations from 2.2.1
and 2.2.2.
2.2.4. Because of 2.2.1-3, including midrad into the standard makes
sense at most as a supplementary datatype in additon to infsup.
But then the stringency of the implementation can be enforced on
the infsup level, and it is better to keep midrad free from
requirements that one might later regret (because of 2.1).
2.3. Lack of uniqueness for providing a clean standard
2.3.1. There is no agreement on the form that the operation should
take in exact arithmetic, not even for the four elementary operations
centered (Henrici-style - cheap, inaccurate) or optimal (equivalent to
infsup, but more costly). Options multiply if also rounding issues
are addressed.
2.3.2. In finite-precision arithmetic, there is no natural notion of
a hull for midrad intervals. A choice of a specific hull operation
is possible but arbitrary from a mathematical point of view.
2.3.3. It is difficult to specify stringent accuracy requirements.
No known scheme both guarantees that high accuracy is achieved and
that implementation is easy and preserves some sort of efficiency.
There is no literature at all abut these issues.
2.3.4. Because of 2.3.1-3, including midrad into the standard makes
at best for either very weak standardization of midrad functionality,
and at worst creates something that cannot be satisfied efficiently
at all. Due to lack of experience, the latter is likely to happen
when stringent demands are made without sufficient theoretical and
experimental support.
2.4. Efficiency issues (see also 2.1.5)
2.4.1. There was an argument that midrad needs only a few digits for the
radius, and hence can be a memory-saving device. However, there are no
applications in sight that are so large that memory would be an issue.
Moreover, a realization of this advantage could only come from a
hardware implementation. But how this could be more efficient
(in terms of speend and chip size) than an infsup version for the
square root, say is an enigma.
2.4.2. A few-digit midrad arithmetic overestimates uncertainties
unnecessarily. Let e be the smallest nonzero radius for an interval
with midpoint 1. Then the product of n intervals 1+-e, computed
sequentially with centered arithmetic and outward rounding, is 1+-me,
where m=2n+1, more than twice as wide than the corresponding infsup
interval. With optimal arithmetic, it is only slightly better, with a
radius of m'e, where m'=2n-2, asymptotically again a factor of 2 off.
In view of the assumption that e has only a few bits, this is a
significant factor.
2.4.3. To have an advantage in speed or memory over infsup, one can
allow only a few bits for representing a radius, which plays havoc
with accurately representing simultaneously innocent intervals such as
[-1,10]. Thus splitting the interval [-22,10] in the middle leads
to double counting of a significant interval near -1.
In multiple dimensions, this effect magnifies exponentially.
2.4.4. A branch and bound code that has to work with midrad-only
arithmetic will have to cover the region close to an interior corner
of a box in the worst case an exponential number of times, unless
the box boundaries are very carefully selected (which would have to
be a research topic). This worst case is attained if the solution
sought actually lies in this area - it must then be found exponentially
often!
2.5. Lack of reproducibility
2.5.1. In finite-precision midrad arithmetic, not even inclusion
monotony is guaranteed; at least it is an open research question
whether one can define a reasonable implementation which is
inclusion monotone. Thus narrowing an interval may lead to
worse bounds of some function of it.
2.5.2. Because of the lack of uniqueness discussed in 2.3,
one can't rely on _anything_ when switching between
different implementations of midrad.
2.5.3. Because of the differences discusssed in 2.2 and 2.5,
one can't rely on anything when switching between an implementation
supporting infsup and one supporting midrad-only.
2.6. Against midrad-only as a possible option
Nothing at all has been thoroughly explored about the consequences of
being forced to use midrad-only arithmetic in conventional interval
algorithms, since nobody has been using it in the past.
Therefore a standard that allows a conforming midrad-only implementation
requires _all_ past algorithms to be reanalyzed for their effects
with such an implementation.
One can't rely on _anything_ anymore when switching between different
implementations, one supporting infsup and one supporting midrad-only.
It is difficult to imagine a worse service to the interval community.
2.7. Uniformity of the standard
2.7.1. Because of the issues discussed above, the requirements
for midrad would on the whole have to be quite different from those
for infsup.
2.7.2. Thus one would have two almost disjoint standards in place
of two, doubling the work for the committee and for implementors,
without paying much dividend (in view of the other caveats mentioned).
2.8. Conclusion
In summary, the little that might appear promising (but without
any proof of widespread useability having been presented by the
supporters of midrad) is far outweighed by the many problems
inherited by the inclusion of midrad into a standard.
3. Why no nonstandard interval support?
This was argued in full detail in the position paper
A. Neumaier,
Computer graphics, linear interpolation, and nonstandard intervals,
Manuscript (2008).
http://www.mat.univie.ac.at/~neum/ms/nonstandard.pdf
that accompanied the Vienna Proposal. There is also a position paper
by Nate Hayes from January 2009 (I believe), who argued for nonstandard
intervals. Both papers are probably on the 1788 web site.
Since then, no new discussion material surfaced, so both positions
still stand.