Am 19.07.2011 17:07, schrieb Nate Hayes:
Jurgen, Marco,
Here are a couple thoughts (off-list) of Arnold's critique (see below).
Be interested to hear your reactions, as well.
Nate
----- Original Message ----- From: "Arnold Neumaier"
<arnold.neumaier@xxxxxxxxxxxx>
To: "Jürgen Wolff von Gudenberg" <wolff@xxxxxxxxxxxxxxxxxxxxxxxxxxx>
Cc: "Ralph Baker Kearfott" <rbk@xxxxxxxxxxxxx>; "stds-1788"
<stds-1788@xxxxxxxxxxxxxxxxx>
Sent: Tuesday, July 19, 2011 8:46 AM
Subject: Re: Unification of motion 25 and 27
On Sun, July 10, 2011 20:00, Jürgen Wolff von Gudenberg wrote:
Nate, Marco and myself have unified motions 25 and 27.
==================================================================
The new Motion 25+27 is indeed much simpler than Motion 26, but it
violates a basic principle commonly attributed to Albert Einstein
(http://rescomp.stanford.edu/~cheshire/EinsteinQuotes.html):
''Everything should be made as simple as possible,
but not simpler.''
Indeed, in the interest of maximal simplicity, Version 1.5 of
Motion 25+27 became far too sloppy. It does not address necessary
results about nontrivial uses of the decorations.
Instead, the main results claimed (Theorem 3) is in fact false
(see below), leading to wrong conclusions and violating the safety
requirement for interval methods.
Arnold Neumaier
=====================================================================
Detailed critique:
Section 1.1.
There is no discernible difference between functions and elementary
operations, so that the semantics remains unclear. In particular, the
semantics of Definition 1 is appropriate only for decorations of a
single elementary operation. E.g., f(x)=\sqrt(x-x) is everywhere
defined and continuous but f([-1,1]_saf) has the decoration con only.
This is a problem of the overestimation of the subexpression x - x.
Definition 1 does not explain the semantics of all decorations. What is
the difference between Empty_saf, Empty_def, and Empty_ndf?
I think Definition 1 explains Empty_saf and Empty_ndf fairly
self-explanatory, since these results can be obtained directly from,
e.g.,
the arithmetic operations.
For Empty with other decorations, I made an attempt at this in the
Motion 25
by making difference between S(f,X) and T(f,X), where the tracking
decoration T(f,X) is the history. This gives semantics listed in the
table
of the rationale in Motion 25, e.g.
Yes
Section 1.3.1.
Definition 6 would give the decoration saf to an ill-formed literal
constant. Thus ill-formed stuff would become legitimated....
At level 1, what is an ill-formed constant?
In our opinion we don't allow ill-formed itervals => ill-formed constants
are singled out by the compiler.
Definition 7 is not properly formulated, as the formulation given
does not say anything about how to compose subtrees but only how to
compose leaves.
He may be right about this...
In our opinion the definition is ok. The definition of the DET is
recursive.
Moreover, it is not clear whether the tree contains
symbolic information about the expression or only decorated intervals
reflecting the history of evaluating an expression.
I'm not sure what he means by symbolic information (we're not dealing
with
Computer Algebra Systems here).
Yes we agree with you
The propagation rule (1) in Definition 8 is identical to the one used
in Motion 26. Thus the substance of the motion is contained in that
of the (much more carefully formulated) Motion 26, except that only a
subset of the decorations treated there is part of the above motion.
IMHO, we don't need bounded decoration. And at Level 1 we don't need
ill-formed decoration.
We consider this as an advantage of our motion.
Theorem 3 is not obvious but false since for f(x)=sqrt(x-x-1), which
is nowhere defined, we get
f([0,2])=sqrt([0,2]-[0,2]-1)=sqrt([-3,1])=[0,1]
with computed decoration con, which is above the true decoratio ndf.
Theorem 3 is fine, since (I believe) it simply says "the worst
decoration in
the DET is propagated to the end".
Yes
It propagates the decoration of the worst path of the DET from the leafs
to the root.
As I noted recently to John in P1788, I believe John and Arnold are
reading
too much into the wording of Theorem 3 by trying to say it compares the
computed decoration to the actual decoration somehow.
Maybe
But this may need some wordsmithing to clarify.
The containment order discussed in Motion 26 is necessary to cover the
correct propagation behavior.
IMHO, the new revision of Motion 26 does not solve the contradiction
pointed
out by Vincent Lefevre several weeks ago. For example, p_def contains
only
(f,X) pairs where X is nonempty, but p_ein is a subset of p_def? Same
with
p_con and p_emp.
Yes
Also, the theorem does not cover the content one would like
to extract from a decorated computation. Relying only on the statement
of the theorem, one could not conclude anything from a computed
decoration ndf, since the true decoration could have been anything
above it. This would make the decoration ndf useless in branch and
bound algorithms. Thus the theory is incomplete and myust be augmented
to a full set of statements that one can rely on after having computed
a decorated result.
As noted, this is due to incorrect interpretation of the wording in
Theorem
3.
Yes
Section 1.3.2.
The semantics stated is appropriate only for decorations of a
single elementary operation. E.g., f(x)=\sqrt(x-x) is everywhere
defined and continuous but f([-1,1]_saf) has the decoration con only.
What is wrong with that?
This is a problem of the overestimation...
It is not clear how lines 3-6 on p.5 imply (as claimed on line 7)
line 8-10. In fact, the latter lines are meaningless as stated since
(unlike in Motion 26) containment is not defined for decorated
intervals.
See Motion 26 Theorem 5.1 (ii)
Section 1.3.3.
The treatment of intersections and unions is inconsistent.
Remark 1 refers to intersections of decorated intervals although the
introduction before Definition 1 says that decorations are associated
with functions. Intersection is not a function like sqrt.
Trees involving both arithmetical operations and intersections may be
meaningless, e.g., f(x)= x/((x+1) intersect x^2). Definition 7 does
not catch the bug but will give a safe answer for f([1,3]).
What is the bug?
In a B&B algorithm, further bisection of [1,3] gives the pavings similar
to
those in the PDF attached to:
http://grouper.ieee.org/groups/1788/email/msg03570.html
It is not clear why the motion distinguishes between hull and union.
Unlike claimed on line 6 of the section, the set-theoretic union is
not defined everywhere in any useful sense since the union of real
numbers is undefined, and the union of disjoint intervals is not an
interval.
It does not make sense that according to Definition 8,
Empty_ndf union [1,2]_saf = [1,2]_ndf
rather than
Empty_ndf union [1,2]_saf = [1,2]_saf.
Section 1.4.
Definition 9 lacks a condition on the decorations. It would allow
F(xx_d):=sqrt(xx)_saf for every decoration d and every interval xx
to define a decorated interval extension of f(x)=sqrt(x), which loses
decoration information and thus may giver too optimistic results.
That's true.
We have to add the sentence
"The decoration of F is computed according to Def. 7 & 8"
to Def 9.
I don't understad this comment.
Theorem 4 while valid is irrelevant for actual computations.
The isotonicity of a range englosure is nice if one happens to have it
but is not essential. For example, centered forms using slopes are not
isotone but very useful for good range enclosures. Most likely,
isotonicity also fails on efficient outward rounding implementations of
multiprecision intervals.
Theorem 5 has empty content since it says nothing about decorations,
and hence is not a FTDIA.
A true FTDIA must allow to conclude from favorable decorations that
the function has on the input interval certain guaranteed properties,
such as definedness or continuity.
There are contradctions still in Motion 26, so I don't see that motion is
such a theory. Dominque showed me once in private a formulation of FTDIA
that does not use the subset relations in Motion 26. My guess is he's
closer
to a valid theory in this respect.
The statement about comparisons in the last paragraph of the section
is meaningless. Indeed, comparisons are treated inadequately,
the function defined by
f(x)=1-x if x<0, f(x)=x otherwise
is not covered by Definition 7 for an expression tree.
No matter how the comparisons are interpreted, an interval evaluation
will give the wrong decoration saf although the function is
discontinuous. (In Motion 26, this can be handled correctly using the
case function.)
I'm not conviced of the case function in Motion 26.
Nate
Section 2.1.
Line 2 says that a decoration is a pair of a function and an interval,
but according to Section 1 it isn't.
These are our comments...
You may publish it on P1788
Best regards
Jürgen & Marco
--
o Marco Nehmeier, Lehrstuhl fuer Informatik II
/ \ Universitaet Wuerzburg, Am Hubland, D-97074 Wuerzburg
InfoII o Tel.: +49 931 / 31 88684
/ \ Uni E-Mail: nehmeier@xxxxxxxxxxxxxxxxxxxxxxxxxxx
o o Wuerzburg