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

A Revised Neumaier-Pryce Decoration Hierarchy (or, let's track the static)



Nate & all

On 25 May 2011, at 21:31, Nate Hayes wrote:
> I do admit it remains a mystery to me why, having aknowledged all of the
> above, you persist in advocating the v3.01 definitions; At the minimum, this
> will clearly require some disclaimer and/or theoretical excuse to explain
> why IEEE 1788 algorithms may experience failure under certain conditions.
> 
> So yes, I am greatly confused and troubled by your position.

In the context of your intersection.pdf example, my position is merely that using the *point* function
    h(x) = f(x) + g(x)
is OBVIOUSLY correct, on any reasonable decoration scheme, because h(x) is defined at some point if and only if both f(x) and g(x) are defined there. While changing from a point function to an *interval* function
   h(X) = f(X) intersect g(X)
needs machinery to MAKE it work, i.e. a particular rule for decorating an intersection. And all in a context where the value of h(X) has no physical meaning.

So I'm also "confused and troubled by your position". I continue to think we really agree but since I'm having a hard time persuading myself of this I don't know how in h*** I'm going to persuade you of it. On the other hand I agree with you 100%
in the min & max discussion in your recent posting
> (i) Intersection of objects
> ---------------------------
> > We are currently examining the application of decorations to
> > Constructive Solid Geometry (CSG):


HOWEVER the following may help us converge. 

I have been thinking about
- Dominique's and your proposal to put "X is empty" at the top of the hierarchy (D4 in your May 20th draft).
- the "problem to which I see NO satisfactory solution" I wrote about on April 28, extract of email copied below.
I see that I was talking through my hat in the latter. Making "X is empty" and "X is disjoint from Dom f" into two separate conditions seems to solve my problem. And means that inclusion isotonicity holds for decorated intervals, as it should do.

Following discussion with Arnold we propose: do as you and Dominique say, and put "X is empty" at the top of the hierarchy. We call this decoration "ein" for "empty input". 

Now, to preserve the "partial order by containment" that is essential to Arnold's scheme, it seems "X is nonempty" clauses have to be switched from the "higher" decorations to the "lower" ones. That is, in Arnold's "dec.txt" paper one changes the definitions
>  p_saf(f,X): X is a nonempty subset of Dom f, and the restriction 
>              of f to X is continuous and bounded;
>  p_def(f,X): X is a nonempty subset of Dom f;
>  p_con(f,X): always true;
>  p_emp(f,X): X is disjoint from Dom f;
>  p_ill(f,X): Dom f is empty.

to
>  p_ein(f,X): X is empty
>  p_saf(f,X): X is a subset of Dom f, and the restriction 
>              of f to X is continuous and bounded;
>  p_def(f,X): X is a subset of Dom f;
>  p_con(f,X): always true;
>  p_emp(f,X): X is nonempty and disjoint from Dom f;
>  p_ill(f,X): X is nonempty and Dom f is empty.

I got the following relations to Nate's D0 to D4 of (see e.g. his May 20 Property Tracking paper). The boolean triplets are his (D+,D-,C), and a value "-" means don't care.
  ein               = D4 = FFT 
  saf & !ein        = D3 = TFT (and conversely D3 = (saf|ein), and similarly with the others below)
  def & !saf        = D2 = TFF
  con & !def & !emp = D1 = TTF (implies X and Dom f are both nonempty)
  emp               = D0 = FT-
  ill               = D0 & (Dom f is empty), so not covered by Nate's scheme.

If this is correct, it preserve the "partial order by containment" and converges closely to Nate's scheme.

Arnold had a criticism, and I haven't had time to let him check this over before sending, so it may yet be blown out of the water.

Must dash ... appointment for dinner with President Obama. Just kidding, but I have been honoured with an invitation to dinner at high table in St Katherine's College Oxford this evening, after a lecture by a friend, so must go.

Regards

John Pryce



On 28 Apr 2011, at 15:13, John Pryce wrote:
(B)
> Now a problem to which I see NO satisfactory solution. I think it's relevant to the recent discussion whether "emp" should be put at the top of the "quality order" of decorations, above "saf", instead of near the bottom as at present.
> 
> On 19 Apr 2011, at 17:07, Dominique Lohez wrote:
>> I have tried to formulate a alternative approach... I came back to some more fundamental points
>> ...
>> In my understanding of the Nate Hayes' work the the calculation of the F = f(X)
>> where F and X are decorated interval ...
>> 
>> According  to John Pryce and Arnold Neumaier,  the fundamental theorem of decorated interval arithmetic must be satisfied. Thus the following property must hold
>> 
>>   if  bareX \subseteq bareY  then  f(bareX) <=_DI f(bareY)       (*)
>> 
>> Where  <=_DI is some order relation between decorated intervals.
> 
> Relation (*) is "isotonicity". It is important, but quite different from the FTDIA, which says
>   (the exact decorated range of f over bareX) <=_DI f(bareX)       (**)
> 
> For *bare* intervals, both are true, where <=_DI is replaced by \subseteq. That is, for bare intervals X,Y
>   (the exact range of f over X) \subseteq f(X)
> and
>   if  X \subseteq Y  then  f(X) subseteq f(Y).
> 
> Unfortunately I think they CAN'T both be true for decorated intervals. Consider "the decoration of f over X", which Nate (Proposition 4) calls
>  S(f,X),
> and I (eqn (9) in 4.8.3) call
>  dec(f,X).
> I believe they are essentially the same, apart from D0 not being the same as "ill" as noted above.
> 
> There are two "progressions" involved. Let G be the Evaluation Graph of a function f for a given input box X.
> - As one progresses along the nodes v of G, on any path from inputs to outputs,
>  the decoration dec(g_v,X) of the sub-function g_v represented by the current
>  node v can only decrease, in the quality order
>      saf>def>con>emp>ill.
>  That fact is crucial in proving the FTDIA.
> 
> - As X itself starts at Empty and "gradually increases", dec(f,X) can only decrease
>  in a *different* order
>      emp>saf>def>con.
>  (Assuming f is a well-formed function, ill doesn't come into the picture.)
>  Namely, suppose dec(f,X)=saf, so f is defined, continuous and bounded on the
>  nonempty interval X. Then f has the same properties when restricted to
>  any smaller interval X', as long as X' is also nonempty. That is,
>     (X' \subseteq X) and (dec(f,X)=saf) ==> dec(f,X') is either emp or saf.
>  Similarly
>     (X' \subseteq X) and (dec(f,X)=def) ==> dec(f,X') is either emp, saf or def.
>  And
>     (X' \subseteq X) and (dec(f,X)=con) ==> dec(f,X') is either emp, saf, def or con.
> 
> Since these two orders are incompatible, it seems to me it is impossible to construct a <=_DI, in Dominique's notation, that gives useful information and for which BOTH isotonicity and the FTDIA are valid. That's a bummer.
> 
> Can anyone square this circle?
> 
> Regards
> 
> John