Re: Revised version of Level 1 text (draft)
Arnold, Nate, other discussers, and all of P1788
Note to the whole group:
I'm getting back to serious P1788 work after a break, rewriting my v03.1 draft text. Though P1788 as a whole has been relatively quiet, there has been much discussion among a group of about ten people, largely about the decoration system. I personally believe we have about 80% agreement on the main theoretical (Level 1) issues that underlie decorations. There are still important disagreements; only time will tell if full consensus can be found.
Several of this gang of 10 have felt it is time to circulate to the whole group, so I am doing so, but slightly worried lest the issue discussed be seen as "angels dancing on the head of a pin" stuff. It is a technical issue, but a significant one, and such things have to be sorted out. Namely
How should the intersection and union (= interval hull) operations handle decorated intervals?
The gist (see Arnold's 5 Dec 2010 paper, first few paras of 22 Jan revised version of §6, quoted below) is:
These are not interval extensions of point functions, so one needs
to analyze them specially *on the basis of likely applications*.
In 4.8.5 of v03.1 I promised an analysis of them in Annex C but didn't give it, as Arnold reminded me.
(BTW Arnold, I believe IEEE standardese is to say "Annex", not "Appendix" but I stand to be corrected.)
Here's some analysis. HOWEVER... I do wonder if we are looking at this from the right viewpoint.
As described by Arnold below,
> intersection operation must cater for the situation where a function
> ... can be expressed in multiple ways ...
> f(z) = g(z) if g(z) is defined and f(z) = h(z) if h(z) is defined,... (*)
And, I assume for now, f(z) is not defined anywhere else.
I leave "union" for now, just noting that the first of Arnold's two proposed uses of it
> a function ... is expressed for different ranges of an argument by different
> expressions. For example, if
> f(z) = g(z) when z>=0, and f(z) = h(z) when z<=0 ... (**)
looks remarkably similar to the "intersection" situation! I guess the difference is that in (**), domain space is explicitly split by the user in a way the user knows about, in this case into half-spaces z>=0, z<=0. In (*) this may not be the case.
Writing Gf for the graph of a function f --the set of pairs (z,f(z)) in the relevant product-space--this is equivalent to the statement about sets
Gf is a function-graph, and Gf = Gg union Gh.
[Where by definition a subset Gf of (A cross B) is a function-graph iff given z in A there is at most one w in B such that (z,w) in Gf.]
Point A.
--------
Interval implementations have to trust the user to get (*) right. Consider Arnold's example below, which can be written
g(x)= (x1-x2)/(x1+x2)
h(x) = 2/(1+x2/x1) - 1
where x = (x1,x2). A computer algebra system can easily see h is a rearrangement of g, so (*) holds; but no practical implementation will check this at run time--if I suggested such a thing, Nate would flatten me, and rightly so.
So if there is a typo in the code, how will this be revealed?
Point B.
--------
Let (*) hold. Write Dg and Dh for the domains of g and h, and let xx be an input box. Then, whether intersection is appropriate to apply seems to depend on how xx relates to Dg and Dh. Let g(xx) denote the result of interval-evaluating g with input xx, etc.
I think what we are REALLY after is
a tight enclosure of range(f,xx)
plus
some knowledge of the relation between xx and f.
Theory gives these elementary facts:
(a) gg = g(xx) encloses range(g,xx), by FTIA; but is usually bigger.
(b) hh = h(xx) encloses range(h,xx), ditto.
(c) range(f,xx) = range(g,xx) if xx happens to be a subset of Dg.
(d) As (c) with g changed to h.
(e) Df = (Dg union Dh) in all cases.
(f) range(f,xx) = ( range(g,xx) union range(h,xx) ) in all cases.
Now using the AN+JDP (ill<emp<con<def<saf) scheme, let gg and hh become decorated intervals (gg,dg) and (hh,dh).
(i) I think the only situation where intersection is appropriate is when BOTH of dg,dh are in {def,saf}. Then we know xx is a subset of both Dg and Dh (hence of Df). Then (a,b,c,d) above imply
(gg intersection hh) encloses range(f,xx).
And if EITHER of dg,dh is saf, we know f is "safe" on xx; otherwise, at least we know f is everywhere defined on xx.
Hence in this case we can return
(ff,df) = (gg intersection hh, max(dg,dh))
as a decorated enclosure of range(f,xx).
(ii) If dg, but not dh, is in {def,saf} then xx is a subset of Dg so by (a,c), gg encloses range(f,xx). As far as I can see, hh and dh give no further information, whether dh is con, emp or ill. So as far as giving information about f is concerned, I would want to return
(ff,df) = (gg,dg)
(ii')Similarly with g and h exchanged.
(iii) If BOTH of dg,dh are in {emp,ill} then we know xx is disjoint from both Dg and Dh, and hence from Df. If BOTH are ill then by (e) we know Df is empty. So returning
(ff,df) = (Empty, max(dg,dh))
makes sense.
In case (ii), we know range(h,xx) is a subset of range(g,xx). So all we know about hh is
hh encloses a subset of range(g,xx),
which tells us precisely nothing. Therefore I cannot see any sensible meaning for
gg intersection hh
in this case. Similarly with case (ii').
I wonder: have we actually got the whole issue backwards, by asking the question "How should we implement intersection and union in a decoration context?". Should it not rather be "Given what we want to discover, when is intersection appropriate and when should something else be used?"
Why should we have an operation that always does
(gg,dg) intersection (hh,dh) = (gg intersection hh, something) = (ff,df), say,
when for certain values of dg and dh we know ff is totally useless?
Nate, Arnold & others who have thought hard about these things, can you answer my skepticism?
Regards
John
On 22 Jan 2011, at 16:15, Arnold Neumaier wrote:
(replying to Nate Hayes' email of 20 Jan 2011)
> (iii) The counterexample related to Appendix 2 of dec.txt
> ---------------------------------------------------------
>
> This is indeed a valid criticism, and shows that my definition was
> slightly sloppy, so that the intended theorem wasn't valid.
> But it does not affect the current Level 1 text draft since that draft
> is restricted to arithmetic operations, whereas intersection is a set
> operation. At the time where the Level 1 text draft is extended to cover
> the latter, there will also be theorems showing that no case has been
> overlooked.
>
>
> With the insight from the counterexample, Section 6 must be corrected as
> follows:
>
>
> 6. Intersection and Union
>
> The propagation under nonarithmetic operations is unspecified by
> the above definitions of the semantics of decorations; cf. the first
> paragraph of Section 6. This must therefore be analyzed partly on
> different grounds, including important examples of use in algorithms.
>
> In particular, since the set operations intersect and union are not
> operations that would occur in functions, the original semantics of
> decorations must be suitably extended to be maximally useful in the
> applications. Again, the rules are essentially determined by the
> requirements for function enclosures, but allowing more complex
> evaluation schemes than simple expression evaluation.
>
> The intersection operation must cater for the situation where a function
> (or an intermediate term in a function) can be expressed in multiple
> ways as a (possibly not everywhere defined) expression.
>
> For example,
> f(x)= (x_1-x_2)/(x_1+x_2) = 2/(1+q)-1, where q=x_2/x_1.
> The evaluation of the second expression gives the optimal range on
> boxes where x_1 does not contain 0. Depending on the argument, it may
> pay to evaluate both expressions and intersect the results.
> (See Appendix 2 for a worked example.)
>
> Thus if
> f(z) = g(z) if g(z) is defined and f(z) = h(z) if h(z) is defined,
> we must be able to get optimal information on the range of f on zz
> from the available information on g and h on zz by intersecting
> the decorated intervals g(zz) and h(zz). This requires that
> (gg,dg) intersect (hh,dh) = (ff,df),
> where
> dg>dh --> (ff,df) = (hh,dh),
> dh>dg --> (ff,df) = (gg,dg),
> dg=dh -->
> if gg disjoint hh --> (ff,df) = (Empty,emp),
> else --> (ff,df) = (gg intersect dh,dg).
Should that be
else --> (ff,df) = (gg intersect hh,dg).
> The union operator (i.e., the interval hull) must cater for the
> situation where a function (or an intermediate term in a function)
> is expressed for different ranges of an argument by different
> expressions. For example, if
> f(z) = g(z) when z>=0, and f(z) = h(z) when z<=0,
> we must be able to get optimal information on the range of f on zz
> from the available information on g on [0,sup(zz)] and h on [inf(zz),0]
> by taking the hull of the union of the decorated intervals
> g([0,sup(zz)]) and h([inf(zz),0]). This requires that
> (gg,dg) union (hh,dh) = (ff,df),
> where
> df=ill || dg=ill --> (ff,df) = (Empty,ill),
> otherwise
> df=dg=emp --> (ff,df) = (Empty,emp),
> otherwise (with min, max in the < ordering)
> (ff,df) = (ff union gg,max(con,min(dg,dh))).
>
> These rules also ensure that we can obtain valid information by
> evaluating f on zz by splitting: If zz is covered by zz1 and zz2
> then both f(zz) and f(zz1) union f(zz2) (and hence also their
> intersection) are valid enclosures of the range of f on zz, with a
> valid decoration.
>
> For example, for f=sqrt and zz=[-4,4], we get for safe input decorations
> f(zz)=([0,2],con).
> If we split zz1=[-4,-1], zz2=[-1,4], we get
> f(zz1) union f(zz2)=(Empty,emp) union ([0,2],con) = ([0,2],con),
> whereas if we split zz1=[-4,1], zz2=[1,4], we get
> f(zz1) union f(zz2)=([0,1],con) union ([1,2],saf) = ([0,2],con).
>
>
>
> To avoid possible ambiguities in the decoration semantics for
> nonarithmetic operations, I propose to require the following default
> rule:
>
> All nonarithmetic operations that make sense for undecorated intervals
> but are not explicitly motivated and specified by the standard operate
> on decorated intervals by ignoring the decorations. In particular, the
> output is not decorated.
> (So programmers are responsible for checking the decorations before
> applying these operations, thus ensuring that they are aware of what
> they do. Since such operations are used rarely, this seems reasonable.)