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.)