Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Motion P1788/0023.01:NoMidRad -- VOTING PERIOD BEGINS



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.