| Thread Links | Date Links | ||||
|---|---|---|---|---|---|
| Thread Prev | Thread Next | Thread Index | Date Prev | Date Next | Date Index |
Greetings P1788
I had hoped to get some revised standard text out to the group for a vote well in time for Christmas, but sadly that won't happen. There has been much work behind the scenes, which has demanded a serious rewrite of Level 1. There are unresolved issues, but I think I see a logically sound solution to them, so it should not be long before a Level 1 draft appears for discussion and hopefully a vote that will harden it to accepted text.
Here is a progress report on what I see as the main issues:
- The inclusion in the standard of both explicit and implicit interval
types was a big change, but it does not affect the mathematical
definition of intervals or interval operations, so it seems to be a
Level 2 change with repercussions at Level 3 but not Level 1.
- I moved Juergen's (Motion 10.2) material on elementary functions from
Level 2 to Level 1, some while ago, because our basic theory implies that
once a point function is specified mathematically (both domain and values)
it is unambiguous whether a given interval function, in infinite or finite
precision, is a valid interval extension of it. (This is significant for,
say, the general power function x^y at x=y=0.)
- "Exception handling". A serious change is that this is now solidly
Level 1. It was pointed out that that "exception" is no longer a good name,
since it carries overtones of program termination, error recovery in
try-catch blocks, and general "bad news". The more we worked on
decorations the more they became "good news", so for the moment I call
this part the "Decoration system". A better name please, someone!
Decorations started as mainly a promising Level 2/3 mechanism with a
rather fuzzy theory. Thanks to extensive work by Arnold Neumaier and Nate
Hayes it has moved from "mechanism" to "implementable theory". Arnold and
Nate differ on some basic definitions and their consequences; if we cannot
achieve convergence there will need to be a vote.
A big advance was Arnold's seeing that Moore's Fundamental Theorem of
Interval Arithmetic (FTIA) can be extended to a
Fundamental Theorem of Decorated Interval Arithmetic (FTDIA).
For some weeks I have been working on a concise formulation and rigorous
proof of this, and on arranging the text so that material essential to an
implementer goes in the main part while the more theoretical stuff, that
underpins it, goes in an Annex. There are some problems with the proof but
I now think I have a satisfactory solution.
My proof is based on Arnold's formulation, because I find his theory is
clearly specified. I hope that Nate's version also leads to a FTDIA and
its proof, but there are aspects of his theory I currently find unclear.
- I have converted Arnold's Matlab solution of my "decoration challenge"
into a decorated interval class, added quite a few more operations, and
used it to write a Branch and Bound function "bb.m" that produces pavings
on the lines of those Nate has been making. See example attached. It
currently runs under Gnu Octave with graphics by Gnuplot as I haven't
Matlab at home, but the changes for Matlab should be minor. If anyone
wants to try it out (and hopefully enhance it), please ask me.
The interval class currently doesn't do outward rounding as I've not been
able to implement "setround" (probably a 64/32 bit incompatibility of
Octave on Mac OS Snow Leopard). A solution will be most welcome.
I hope this report encourages people that progress with our standard continues to be made despite the lack of new decisions recently.
I think it is time to decide on *constructors* for P1788. Is anyone willing to put forward a motion on that? And, are they more appropriate as a Level 1 or a Level 2 notion?
Best wishes for Christmas.
John Pryce
------------Some technicalities on the decoration system and FTDIA----------
- Both Arnold and Nate have currently standardised on five decoration values
to which Arnold gives the brief names
("best news") saf, def, con, emp, ill ("worst news").
Other schemes are possible; we are considering splitting saf into two,
giving a 6-value scheme.
- Brief statement of the FTDIA:
Theorem.
When evaluating an expression in "decorated interval mode", if
* the input decorated intervals are suitably initialised;
* the decorated interval versions of arithmetic operations handle both
interval and decoration part correctly;
then the decorated interval result encloses the decorated range of the
point function defined by the expression.
Arithmetic operations "handling the interval part correctly" means
enclosing the exact range in the traditional FTIA way.
"Handling the decoration part correctly" means basically the sticky
decoration scheme we have been discussing for some months.
The "decorated range" of a function f over an input interval vector xx
is the pair (r,d) where r is the normal "exact range" of f over xx, and d
is the corresponding "exact decoration" of f over xx, which has a simple
definition.
A pair (r1,d1) encloses a pair (r2,d2) if r2 is a subset of r1 in the
normal set sense and if d2 is *stronger* than (or equals) d1 in the
assertion it makes about f and xx.
(E.g. saf says "the restriction of f to xx is everywhere defined and
continuous, and f is bounded on xx"; def just says "f is everywhere
defined on xx" so saf is stronger than def.
--------------------------Example output of bb.m-----------------------------
This was produced by the calls
octave> f=@(x,y)sqrt(1 - sqr(sqrt(sqr(x)+sqr(y))-3));
octave> T_bb2(f, -4,6.7, -4.9,3.9, 0.4,0.8, 0.05)
Being interpreted, f(x,y) describes the top half of a torus, namely the surface of revolution about the z axis of the semicircle
(x-3)^2 + z^2 = 1, z>=0.
The T_bb2 call asks for a paving to find the set, in rectangle
-4 <= x <= 6.7, -4.9 <= x <= 3.9
where z = f(x,y) satisfies
z in interval bb = [0.4,0.8],
and ceasing to bisect a box when it is smaller than 0.05 in each dimension.
The algorithm summary is basically like Nate's in his position paper:
% if isEmpty(f) then delete X (yellow)
% else if disjoint(f,bb) then delete X (gray)
% else if everywhereDefined(y)
% && in(y,bb) then S = S union X (green)
% else if eps(X) then mark X indeterminate (red)
% else bisect X.
On exit it reported "total no. of boxes processed is 11667".
I chose rather random x and y limits because the resulting irregularity in the boxes is interesting.
Attachment:
torusplot3.pdf
Description: Adobe PDF document