Re: Comparisons and decorations
> Date: Fri, 24 Sep 2010 21:49:34 +0200
> From: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
> To: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
> Subject: Re: Comparisons and decorations
> X-Univie-Virus-Scan: scanned by ClamAV on justin.univie.ac.at
>
> Dan Zuras Intervals wrote:
> >> Date: Fri, 24 Sep 2010 18:31:31 +0200
> >> From: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
> >> To: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>,
> >> 1788 <stds-1788@xxxxxxxxxxxxxxxxx>
> >> Subject: Re: Comparisons and decorations
> >>
> >> Dan Zuras Intervals wrote:
> >>>> Date: Fri, 24 Sep 2010 12:48:38 +0200
> >>>> From: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
> >>>> We hadn't yet discussed the behavior of decorations for nonarithmetic
> >>>> operations; Motion 8 was silent on these, but in the present context
> >>>> it must be decided. The rationale is as follows:
> >>>>
> >>>> Decorations are primarily there to allow making decisions about
> >>>> nonexistence, existence, and uniqueness correctly. This is the only
> >>>> place where I think they are essential for the correctness of interval
> >>>> programs.
> >>>>
> >>>> Therefore, one needs to ensure that a test for disjointness,
> >>>> containment, or interiorness, is never false positive.
> >>>> This rule is enough to decide all ambiguities for these
> >>>> three comparisons.
> >>>>
> >>>> . . .
> >>> Finally, on the issue of false positives.
> >>>
> >>> I don't think this can be prevented on ANY predicate.
> >> For many predicates it cannot be prevented, and this is
> >> sufficient reasons to ban them from the standard.
> >
> > Well, for any predicate that depends on the truth
> > (or falsity) of a comparison like a < b, that can
> > be turned into a <= b by rounding errors.
> >
> > I'm pretty sure people will want to be able to
> > test interval1 < interval2. And its compliment.
>
> Unlike you, I used intervals for many years, and know how others
> (though not how everyone) use intervals. Of course, one can make
> arbitrary use of interval comparisons, but the purpose of a standard
> is not to promote arbitrary use but to promote good use with a
> consistent semantics.
>
> I never needed to compare whether some interval is smaller than
> another interval, precisely since this information is typically
> useless for the reasons you mention. So there is no incentive to
> provide such an operation in the standard.
>
> However, I needed in crucial places the three comparisons
> disjoint, subset, interior,
> and it is important that these are safe in the manner I describe.
>
>
>
> >
> >> For the three predicates that matter, it _is_ possible to the
> >> extent needed without any difficulty. And it is _necessary_
> >> for interval algorithms to make decisions. Therefore it _must_
> >> be ensured by any standard that deserves its name.
> >>
> >>
> >>> Remember we are computing our intervals within an
> >>> arithmetic of finite precision & range. Therefore,
> >>> we risk expanding our intervals beyond their strict
> >>> range every time we touch them. Sometimes by a
> >>> little. Sometimes by a lot. It depends on both the
> >>> operations involved & the precise values of its
> >>> operands.
> >> Disjointness can only change from true to false by overestimation.
> >> Thus overestimation is harmless, since it does not introduce false
> >> positives.
> >
> > I believe that is true.
> >
> > Still, the opposite assertion, that two intervals have
> > a common intersection is also an important test. In that
> > case rounding errors can create a common intersection
> > where none really exists.
>
> No, this is not an important test. Nothing of significance in
> theory depends on it.
>
> The situation is similar to the predicate isIn. It is inconsequential
> for interval arithmetic that the test x isIn A leads to false positives,
> because nobody seriously doing interval computations concludes from
> a possibly overestimated A that x belongs to A upon such a test.
>
> However it is essential that the test does not lead to false negatives.
> Indeed, this is precisely the condition ensured by outward rounding.
>
> One needs to make sure that one does not lose containment, but gaining
> containment is unavoidable.
>
> Now x isIn A is equivalent to [x,x] has a common intersection wit A.
> So this may have false positives but not false negatives.
>
> In other words, disjointness, which is wnat one commonly tests,
> must not have false positives but may well have false negatives.
>
>
> The moral of this is that for interval computations, a predicate
> and its negation are not on equal footing.
>
> The standard must ensure that the answer which has the most
> decisive consequences must never be wrong, and require a
> corresponding semantics.
>
>
>
> >> Containment and interiorness can only change from true to false
> >> when the first argument is overestimated. Thus this is harmless,
> >> since it does not introduce false positives.
> >>
> >> But it can be changed from false to true when the second argument
> >> is overestimated. Thus this is potentially dangerous, since it may
> >> introduce false positives. However, in the applications, the second
> >> argument is always a fixed interval _known_ not to be overestimeated.
> >> Thus (once the semantics is precisely defined), users cannot go wrong
> >> in applying it as long they adhere to the semantics.
> >
> > It kind of depends on how you define these things.
> > In general, I believe assertions based on <= are
> > more robust than assertions based on <.
>
> There are standard definitions for
> disjoint, subset, and interior,
> where a mathematician cannot tamper with.
>
> I don't care about < and <= since these cannot be used in a useful way.
> The standard should ban these, for the sake of transparency and
> simplicity.
>
>
>
> >> Nothing can save users from applying constructs outside of their
> >> defined semantic meaning; so we don't need to care for that.
> >> We only need to ensure that the semantics comes clearly and
> >> unambiguously across, and this is the case the shorter and the more
> >> conceptual the formulation.
> >>
> >>
> >>
> >>> Remember also that rounding errors are not random.
> >>> Nor are they distributed randomly in any given string
> >>> of calculations.
> >> This does not matter at all in the present context.
> >
> > Only in so far as we are counting on a <= b never
> > becoming a > b when a & b go through the same
> > calculations.
>
> I am not counting on properties of comparisons that are useless
> in practice. It is irrelevant how these are standardized, and
> therefore they have nothing to do in a standard. (They fill a
> much needed gap, as you quoted Kahan!)
>
> I want to count on properties that are needed, and these properies
> are precisely that comparisons for disjoint, subset, and interior
> have no false positives.
>
>
>
> >>> So, even in the case of xx \interior yy where both xx
> >>> & yy typically go through the SAME calculations to
> >>> arrive at the comparison, one may have expanded a
> >>> great deal more than the other.
> >> In those applications where this needs to be checked, to get an
> >> existence assurance of a zero, say. yy does not suffer any
> >> overestimation since it is an interval _chosen_ by the user
> >> (or algorithm) to mean this domain, not to mean a computed range.
> >
> > Hmm. Perhaps I misunderstand then. I thought there
> > were narrowing algorithms which counted on the
> > continued intersection getting narrower. Namely that
> > xx(i+1) \interior xx(i) at each stage. Or at least
> > each stage was confined to xx(i+1) \intersect xx(i).
> >
> > Do I have that wrong?
>
> Under the typical circumstances, as soon as you have F(xx) interior xx,
> you know that xx contains a solution. In this situation, xx is an
> arbitrary domain, independent of the history how it was created,
> whereas F(xx) is an interval extension of the Newton operator kind.
>
> Thus once you know xx(i+1) \interior xx(i) without false positive
> with respect to overestimation in xx(i+1), you can be sure that xx(i)
> (no matter how it was computed) contains the solution.
>
>
> >
> > For the above concerns, let's say we have aa(0) =
> > [alo(0),ahi(0)] & bb(0) = [blo(0),bhi(0)] & we implement
> > the predicates
> >
> > disjoint(aa,bb) = (ahi < blo) || (bhi < alo)
> > contained(aa,bb) = (blo <= alo) && (ahi <= bhi)
> >
> > Now let's start with ahi(0) < blo(0) so that disjoint is
> > true & contained is false.
> >
> > It is easy to see that as we go along in calculations
> > producing first aa(1) & bb(1) then aa(2) & bb(2) & so on,
> > that there may come a time when we no longer have
> > ahi(i) < blo(i) but ahi(i) == blo(i).
> >
> > Then disjoint would become false & contained would remain
> > false.
>
> Yes, but does it matter? You cannot draw any useful consequence from
> the facts that you asserted.
>
> A predicate is only useful if establishing it gives you useful
> information about something else not yet in the predicate itself.
>
> Thus it is theory that tells you what sort of predicates are useful,
> namely those that arise as part of the hypothesis of a useful theorem.
>
> I have never seen a theorem drawing a nontrivial conclusion from
> having a nonempty intersection, or fron mit being a subset of
> another subset, or from not being in the interion of another interval.
>
> Neither have I seen a theorem giving useful information given that
> an interval is smaller than another one.
>
> Therefore I conclude that these comnparison serve no positive purpose,
> and hence
> (i) can tolerate false positives,
> (ii) are irrelevant for a standard.
> Most of the comparisons currently under voting are of this kind.
> Therefore I recommend not to vote for their acceptance.
>
>
> Of course, if anyone listening can point to such theorems, I'd like
> to know; but I'd be very surprised.
>
>
> > So we will have gone from
> >
> > disjoint(aa(0),bb(0)) = true &
> > contained(aa(0),bb(0)) = false
> >
> > to
> >
> > disjoint(aa(i''),bb(i'')) = false &
> > contained(aa(i''),bb(i'')) = true.
> >
> > I don't know if this constitutes a danger to a correctly
> > written interval program but as I believe we want both
> > predicates in our arithmetic, it must be accounted for.
>
> Since nothing follows from a violation of an assumption of a theorem,
> all this has no consequences at all.
>
>
> Arnold Neumaier
First, I grant your greater expertise when it comes
to interval issues. You all have greater expertise
in this. I'm just the floating-point lurker here. :-)
Next, I see I was unclear in my text above. When I
was speaking of a <= b versus a < b I was not (except
in one case) speaking of interval less than. I was
speaking of interval comparisons which are constructed
of the FLOATING-POINT predicates a <= b or a < b.
Sorry about the misunderstanding.
Next, you continue to assert that disjoint, subset,
& interior are the only (numerical) predicates that
should be in an interval arithmetic.
If this is so I understand why the edifices created
by motions 13 & 20 have no meaning for you. They are
unneeded in a world with only these 3 simple numerical
predicates.
(I qualify that with the word 'numerical' to distinguish
them from predicates involving decorations.)
Next, let me guess as to how the predicates disjoint,
subset, & interior are written. For aa = [alo,ahi] &
bb = [blo,bhi], I'm guessing they are something like
disjoint(aa,bb) = (ahi < blo) || (bhi < alo)
subset(aa,bb) = (blo <= alo) && (ahi <= bhi)
interior(aa,bb) = (blo < alo) && (ahi < bhi)
Do I have that right?
Then the example I cited in my earlier note is one in
which iteration turns aa(0) & bb(0) from
disjoint(aa(0)),bb(0)) = true &
subset(aa(0)),bb(0)) = false
into aa(i'') & bb(i'') with
disjoint(aa(i'')),bb(i'')) = false &
subset(aa(i'')),bb(i'')) = true.
Are you OK with that?
I can give you numbers. It can be done in one step.
Its kind of cute.
If I have the definitions correct one cannot go from
disjoint to interior in 754 arithmetic. But disjoint
to subset can happen.
Is that all still OK?
I am concerned that in a different context the false
positive on subset may lead one to believe that a
solution exists where one does not.
But we now enter your area of expertise...
Dan