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

Re: Version 2.11, Proposal for interval standardization

Arnold Neumaier wrote:

Sylvain,
- I find it strange to mention "standard intervals" and "non standard intervals". 

The reason is that I want nonstandard intervals to be supported in a
minimal way that enables someone interested to create a
standard-complying implementation of Kahan or Kaucher arithmetic.


I understand.
I was just hoping that there could be a more minimal approach to this :)


- 1.5.6 : anyInterval(l,u) : what happens if e.g. l>u ?
Should some "undefined behavior" notion be defined somewhere and used here? 

Nothing special happens. This is the difference between 1.5.5 and 1.5.6.


I noticed the difference, but still: what happens if I do it?
Is an implementation allowed to stop the program and issue an error
(in debug mode, for example)?
In the C++ standard, this would typically be phrased by referring to
undefined behavior.



- 2.6 "Exact expressions" : I was wondering what the reason of this was.
 I see 2 reasons :
* being able to parse a complete expression: it seems like this belongs to 
   the language level.
* being able to get tighter intervals for constants which you want to specify as simple expressions.
The reason is that I had come across real applications (to conjectures in pure math) generated by computer-algebra systems where constants were quotients of very long integers or algebraic numbers defined by expressions. 

Computer-assisted proofs is one of the important applications of
interval techniques, and should be well- supported by the standard.


Fine.  I understand the need for allowing sharp interval constants
generated from constant expressions.

Related to this (and not addressed by your current proposal),
it would be nice to know if there are applications where having shaper
intervals for constants is *required*, e.g. getting the tightest interval.

Do the computer-assisted proofs that you mention *require* those
shaper intervals, for example?



This is a good thing, but I think we can generalize
it to any kind of sub-expression, not only those exact "constant" expressions. The idea is that we should allow an implementation to produces tighter results for combined operations when it can do so. For example, it should be possible to turn the function "(x/7)*7" into "x", or turn "sqrt(x*x)" into "abs(x)", since these transformations produce proovably tighter intervals compared to the step-by-step evaluation, and the containment guarantees are still 
   there for the whole function.
Unless I miss some arguments which would make these transformations invalid for some applications, I think that we should mention it, otherwise we may 
   prevent some optimization opportunities.


This is difficult to specify in a standard, since the list of useful
transformations is difficult to establish, and the demands placed on the
implementor is significantly increased. Moreover, sometimes, different
equivalent formulations have different advantages, so that there will
be hardly an agreement of what to demand. Such things are better handled
in a context like automatic differentiation type software, which
requires different expertise than those have who are likely to create
a good interval implementation.

We must place a limit to what to include in the standard.
My recommendation is of course my personal judgment, but I tried
to put the border where it benefits most.


Maybe I was not clear enough.  I am not suggesting that the standard should
*require* those transformations, I am suggesting that it *allows* them.
And this is currently not the case in your proposal, except in this paragraph,
which sounds strange to me, hence my suggestion to generalize it.
My suggestion is to remove the special case of those constant expressions
(which in fact only *allows* shaper intervals in this case), and replace
it by a general authorization for the implementation to perform any such
transformation.  This could be phrased, I think, without any explicit list
of transformations (which I agree would not be realistic).
I can suggest the following wording:

 For any expression combining functions over a set of input intervals,
 an implementation is allowed to return a shaper interval than the one
 required by the involved functions taken separately, provided that the
 containment property is still ensured for the result of the expression,
 for all possible real values in the input intervals.

 Examples of valid such transformations:

   - (1/interval(3))*3   ->  interval(3)
   - (x/2)*2             ->  x
   - sqrt(square(x))     ->  abs(x)
I expect to have a new version of my proposal ready towards the end of this week, reflecting these comments and many others I received off-line. 

Excellent!  Thank you Arnold for this hard work.
I am looking forward to this next version.

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature