Ralph Baker Kearfott wrote:
The motion discussion period has run out on October 5. Although
there are several other issues also presently past their discussion
period,
those are not closely related to this issue, and it is important
that this issue be decided soon. Thus, I have decided to bring this
issue to a vote separately.
Here, let us agree that "support" in this motion means that
operations on the object, possibly including accuracy and
reproducibility requirements, are explicitly defined in the
standard. Also, by "nonstandard intervals," let us agree that
this means Kaucher arithmetic. (Otherwise, one might think
"nonstandard"
meant "anything not in the standard," something that would
not make sense in this context.)
The voting will continue until after Sunday, October 31, 2010, or
until such time as the Voting Tabulator deems is appropriate.
Juergen: Please post this information on the web page.
Guillaume: 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.
----------------------------------------------------
Since the precise meaning of the motion has been challenged,
let me note that when I formulated this, it was explained in my
mail from September 14 as follows:
<begin quote>
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.
<end quote>
Note also the response by Nate Hayes from September 15, which confirms
this interpretation:
<begin quote>
this is also my conclusion of Arnold's position, i.e., he does not
oppose that users and implementers should use mid-rad or Kaucher
arithmetic, just that these aspects of interval arithmetic should not be
supported or endorsed by P1788.
If enough people in P1788 feel so strongly about this as does Arnold and
wish to prohibit mid-rad or Kaucher arithmetic, this is fine with me and
I would continue to help build such a standard.
<end quote>
Thus the more explicit meaning of the motion is the following:
======================================================================
It is proposed that, apart from conversion issues, approximately to
the extent specified in the Vienna Proposal, specifications shall be
provided by the final standard text only for infsup 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.
======================================================================
For the sake of definiteness, I attach as a position paper this
revised formulation of the motion text, together with a rationale
for accepting the motion, compiled from the past discussion.
I believe that even those promoting midrad and Kaucher arithmetic
in this forum will be better off not having a standardized -- hence
rigid and for a long time incorrigible -- framework, to which they are
forced to stick to be standard compliant.
The main point was and is to end wasting people's time on issues
that are either not necessary to have in any standard or
far from ripe for inclusion into the present standard.
There are more than enough issues in the infsup case that demand
our attention and energy.
Accepting the motion 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.
The motion standardizes just the parts that are widely used in
practice, and for which half a century of experience is available.
In view of the lack of extensive practical use, standardizing formats
different from infsup comes one decade too early; it is likely that
we'd make poor decisions that are regrettable later.
It makes only sense to standardize something that has been used a lot,
so that all design tradeoffs are known and well-understood. This is
the case for infsup arithmetic on intervals defined as closed and
connected sets, but not for the other options.
Standardizing something too early is likely to introduce bad design
features that are hard to eliminate later, and stifles exploration
of the best possibilities.
Arnold Neumaier
Interval types in the standard
------------------------------
Position paper by Arnold Neumaier (Vienna)
October 11, 2010
It is proposed that, apart from conversion issues, approximately to
the extent specified in the Vienna Proposal, specifications shall be
provided by the final standard text only for infsup 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.
Rationale
---------
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. An infsup representation 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. (See Section 2 for details.)
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.
1.8. It makes only sense to standardize something that has been used a
lot, so that all design tradeoffs are known and well-understood. This is
the case for infsup arithmetic on intervals defined as closed and
connected sets, but not for the other options.
1.9. Standardizing something too early is likely to introduce bad design
features that are hard to eliminate later, and stifles exploration
of the best possibilities.
1.10. Conclusion:
In view of the lack of extensive practical use, standardizing formats
different from infsup comes one decade too early; it is likely that
we'd make poor decisions that are regrettable later.
2. Past applications
2.1. Applications of mid-rad arithmetic
2.1.1 The midpoint and radius of intervals and interval vectors are of
significant importance in the theory and analysis of interval
algorithms. However, the 1788 standard is not supposed to standardize
mathematical concepts, but their implementation in software or hardware.
Thus what counts is only the use or usefulness of a midrad datatype
for actual computations.
2.1.2. None of the theoretical uses of midpoint and radius translate
into applications where an arithmetic for a mid-rad interval datatype
would be more efficient than the standard inf-sup datatype.
2.1.3. The only significant past use of mid-rad arithmetic in
applications has been in fast interval matrix-vector and matrix-matrix
computations with large interval matrices whose coefficients have
narrow widths. However, these applications do not use a mid-rad datatype
but separate real midpoint matrices and radius matrices constructed on
the fly from inf-sup intervals.
2.1.4. The P1788 standard only standardizes interval operations
resulting in single intervals; at least no discussion so far was
about standardizing interval BLAS within P1788 (which indeed would be
unreasonable to do). The applications in 2.1.2 are, however BLAS2
or BLAS3 operations, hence do not fall under the P1788 topics.
2.1.5. For single intervals, the techniques under 2.1.2 are no longer
superior to inf-sup computations; they are both more costly and less
accurate. Moreover, the efficiency of the techniques under 2.1.2
crucially depends on this separate representation of midpoint and
radius. Thus the existence of a mid-rad datatype for single intervals
does not help the slightest in implementing these fast techniques.
2.1.6. In particular, nothing at all is lost for the applications
under 2.1.2 if P1788 mostly ignores midrad interval arithmetic.
The issue must be considered only when (a new committee is) working
on an interval BLAS standard at the BLAS2 or BLAS3 level.
2.2. Applications of nonstandard intervals
2.2.1. Nonstandard intervals in the form of Kaucher intervals or modal
intervals have a number of applications to tolerance problems,
computer graphics, robotics and control.
2.2.2. In virtually every case, the applications do not really depend
on nonstandard intervals, and can just as efficiently be realized using
standard intervals.
2.2.3. Great care has to be taken not to get unsafe results when using
nonstandard intervals, since deductions are based on theorems whose
statements are sometimes imprecise and whose proofs are not carefully
argued in the literature.
2.2.4 All this is 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.
2.3. Conclusion
There is no evidence that applications bwenefit from standardizing
anything beyond inf-sup interval arithmetic.
3. Why no midrad support?
3.1. Lack of experience and research to support a standardization
3.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.)
3.1.2. Most literature on midrad arithmetic is purely theoretical,
assumes exact arithmetic, and is concerned with the four binary
operations + - * / only.
3.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.
3.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.
3.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.
3.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.
3.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.
3.1.8. A need for standardizing exists only if different versions are
so widely used that lack of standardization impedes progress.
This is not the case for midrad arithmeitc. In this case,
standardization by elimination of one of the options would even
be unwise, since different midrad operation definitions have
different uses.
3.1.9. Because of 3.1.1-8, including midrad into the standard is
premature and prone to make poor choices.
3.2. Lack of support for handling wide intervals
3.2.1. Midrad cannot support half-infinite intervals such as [0,inf],
very important for global optimization.
3.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.
3.2.3. It is easy to simulate midrad arithmetic in terms of infsup,
while the converse is impossible because of the limitations from 3.2.1
and 3.2.2.
3.2.4. Because of 3.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 3.1).
3.3. Lack of uniqueness for providing a clean standard
3.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.
3.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.
3.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.
3.3.4. Because of 3.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.
3.4. Efficiency issues (see also 3.1.5)
3.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.
3.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.
3.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.
3.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!
3.5. Lack of reproducibility
3.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.
3.5.2. Because of the lack of uniqueness discussed in 3.3,
one can't rely on _anything_ when switching between
different implementations of midrad.
3.5.3. Because of the differences discusssed in 3.2 and 3.5,
one can't rely on anything when switching between an implementation
supporting infsup and one supporting midrad-only.
3.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.
3.7. Uniformity of the standard
3.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.
3.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).
3.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.
4. 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.