Re: A question Re: Level 1 <---> level 2 mappings; arithmetic versus applications
> Date: Wed, 30 Jun 2010 08:23:11 -0500
> From: Ralph Baker Kearfott <rbk@xxxxxxxxxxxx>
> To: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
> CC: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>, stds-1788@xxxxxxxxxxxxxxxxx
> Subject: A question Re: Level 1 <---> level 2 mappings; arithmetic versus
> applications
>
> Dan,
>
> On 6/30/2010 02:38, Dan Zuras Intervals wrote:
> >> From: "Nate Hayes"<nh@xxxxxxxxxxxxxxxxx>
> >> To: "Dan Zuras Intervals"<intervals08@xxxxxxxxxxxxxx>,
> >> "Christian Keil"<c.keil@xxxxxxxxxxxxx>
> .
> .
> .
>
> > Let the mapping from level 1 to level 2 be defined by the
> > narrowest mapping possible. That is, of all the objects
> > that exist in your representation that represent supersets
> > of a given level 1 interval, let the mapping be to some
> > object which is a subset of all of them. There may be
> > many such mappings. And the are all, of course, equal in
> > the above sense.
> >
>
> I am wondering whether or not there may actually be "many such
> mappings," or whether specifying the object which is "a subset of all
> of them" specifies the mapping uniquely. For example, in the
On the contrary, for the forms we are concerned with here
they have the property that they 'want to' define their
upper & lower bounds by the sum of 2 or more elements.
There may be many representations that sum to the same
number. The only thing that we would consider 'unique'
about them would be their sum, something that would be
the defining characteristic I speak of.
For example, given an interval whose best representation
in a given floating-point type has the lower bound 'a' &
upper bound 'b', a representation (mid,rad1,rad2) that
represents the interval [mid+rad1,mid+rad2] may have many
mid x rad1 x rad2 triplets such that both a = mid + rad1
& b = mid + rad2.
And ALL OF THEM would be subsets of any representable
interval that contains our desired interval. And ALL OF
THEM would represent the SAME interval as far as we are
concerned. And ALL OF THEM would be considered equivalent
as far as we are concerned SO LONG AS all of them behave
in the same way when they participate in arithmetic or
non-arithmetic operations.
It is all we need.
Another possibility that has been hinted at is something
along the lines of a (mid,eps1,eps2) that represents the
interval [mid-eps1-eps2,mid+eps1+eps2]. This is somewhat
less flexible in that it only represents things in the
same way that (mid,rad) represents [mid-rad,mid+rad]. But
there may be many such mid x eps1 x eps2 for any given
a = mid - eps1 - eps2 & b = mid + eps1 + eps2. And there
may be good numerical reasons for wanting to split things
up in this way.
I don't know. But there is nothing in this 'only speak at
level 1 + level 2' approach that eliminates the possibility.
Nor should there be.
> inf-sup representation and 754 arithmetic, rounding the lower bound
> down and rounding the upper bound up gives a uniquely defined interval,
A uniquely defined INTERVAL, yes. It need not be a
uniquely defined REPRESENTATION of that interval, though.
> it represents one such mapping, so any such object will have to
One such mapping for an inf-sup form, perhaps. And it
might be that inf-sup forms are the only representation
for which that is true. Or stated another way, it might
be that inf-sup forms are the only ones that suffer from
that limitation. :-)
> include the object so obtained, and there are no proper subsets constructed
> from machine numbers that contain that object. Therefore, the
Well, I've already answered that in the negative.
> mapping in the context of inf-sup and 754 is unique (and hence would
> lead to an arithmetic that is reproducible across implementations).
Actually, except for having a representation for infinity
in our floating-point arithmetic, we need not mention 754
at all. And we would STILL be reproducible across any
implementations that share that floating-point type.
>
> I suspect a similar uniqueness holds for various mid-rad schemes, or
> is the interplay between the midpoint and radius a sticking point?
A similar uniqueness can be MADE to hold for mid-rad forms.
This is the whole point.
As for the interplay between midpoint & radius, this is
where Ian's example comes into play.
The natural approach to a mid-rad form in which mid x rad
represents [mid-rad,mid+rad] cannot represent some [a,b]
down to the last bit as tightly as an inf-sup form.
This is why I mentioned that we might want to loosen the
'tightest representable interval that is a subset of all
other representable intervals' restriction.
I think it might be possible to define the restriction as
either a subset of all other representable intervals that
contain the desired interval or, at most, having one bound
be 1 ULP wider than that.
I think that works for mid-rad forms but I'm not sure.
It might be necessary to permit BOTH bounds to be capable
of being widened but as much as 1 ULP. But I cannot find
any examples.
Any mid-rad guys out there want to weigh in on this?
Loosening this 'tightest possible subset' restriction is
not as mathematically appealing but it might make things
easier on the mid-rad folks.
We would still have to demand that any given desired
interval be loosened in exactly the SAME way, though.
Otherwise we would lose our 'all representations of this
interval are equivalent for arithmetic' thing.
And loosening this restriction also has the property that
implementations that use mid-rad forms & take advantage
of this loosening are distinguishable in their arithmetic
from inf-sup forms & other mid-rad forms that find a way
NOT to use this loosening.
But by no worse than 1 ULP in any given operation.
Not a great result, I grant you, but it might be acceptable
to us if it brings the mid-rad folks on board.
It is something we need to decide.
>
> > Now, with mappings back& forth we can define arithmetic.
> >
> > Let any operation be defined by mapping its operand(s) to
> > level 1, applying that operation there, finding the
> > contiguous hull of the result there& mapping that result
> > back into your format in the tightest sense as defined
> > above.
> >
>
> By the way, I've also been wondering about whether or not
> discussing whether or not Intlab's use of mid-rad is a bit
> of a red herring. In particular, we are defining arithmetic
Of course it is a red herring. At least in so far as
discussing whether or not we want to allow it to conform.
As for discussing whether or not we like some feature of
an existing interval implementation, I think that is VERY
MUCH relevant to our discussion. And, while I am
unfamiliar with Intlab's details, it seems to be a very
good implementation & worthy of our sincerest flattery by
immitation (of those worthy features only, that is).
> operations and conversions. Intlab's matrix multiplication is
> a kind of "application" in which the result of a large number
> of operations is returned. Just as in floating point computations
> based on 754, error can accumulate beyond the unit roundoff
> error specified by 754, the resulting intervals from a string
> of computations cannot be expected to obey accuracy or other
> properties specified by an interval arithmetic standard, except
> for (if we so decide) conversion from its lower level representation
> to a higher-level one (or visa versa, for input). (This is, of
> course, assuming we do not define the function value(s) computed in
> the application as a required or recommended function in our
> standard.) The one
> thing that such an application must obey, to satisfy the "proof"
> philosophy of interval computations, is that it include
> the exact result. Thus,
> whether or not Intlab used mid-rad, inf-sup, or some weird
> elliptical arithmetic such as mid-mid-rad-rad, would seem to be irrelevant.
> (However, one goal of our standard is to make the writing of such
> applications easier, more portable, and easier to debug or see their
> correctness -- I'll review our PAR.)
>
> Best regards,
>
> Baker
>
Yes.
It is true that computing matrix multiply in this way
is not guarenteed to produce a result within 1 ULP of
the correct answer in any floating-point or interval
system.
Still, computing INTERVAL matrix multiply via the means
of 'midpoint multiply + Jacobian radii + accounting for
roundoff errors' is VASTLY faster than computing with
blind inf-sup operations. And it produces a VASTLY
narrower interval matrix in many cases. And STILL not
as narrow as the 'narrowest to 1 ULP' matrix that is
the best possible representation of the result.
There are many examples of 'canned' operations like this
that, while not easily definable, are nonetheless worthy
to be in our list of things that should be permitted to
conform.
I don't know how you solve the problem of defining what
is worthy or what is not in the interval context.
I don't know how you solve the problem of defining what
is worthy or what is not in the floating-point context
either.
It is a hard thing for a standards body to do & I can
offer no worthy advise on how to do it.
But let's solve the problems WE CAN solve & see if they
help at all in narrowing the scope of those we cannot.
OK?
Dan