Re: A question Re: Level 1 <---> level 2 mappings; arithmetic versus applications
Dan Zuras wrote:
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.
Makes sense.
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 think this is hugely attractive, if we can pull it off.
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.
I don't really consider myself a "mid-rad guy," but I am interested in this
discussion. :-)
These are a few of my initial (random) thoughts:
John has previously made the observation that there is an exact mapping from
Level 2 mid-rad interval to Level 1 interval. Of course, once at Level 1
there is then also an exact mapping from mid-rad to inf-sup (or vice-versa).
So the only conversion that requires care is mapping back from Level 1 to
Level 2. However, it seems there is some Level 1 mid-rad interval
corresponding to some Level 2 mid-rad interval that is provably the tightest
possible Level 2 enclosure, so long as that Level 2 enclosure is represented
by a midpoint and a radius.
This makes me think it should be feasible to not even loosen the "tightest
possible subset" restriction, if the definitions are made carefully. It does
seem that "tightest possible subset" might depend on the Level 2 format,
though.
For example, any given Level 1 interval [a,b] has the property:
[a,b] = (m;r)
where (m;r) is a mid-rad interval and m=(a+b)/2, r=(b-a)/2. There is then a
tightest possible Level 2 inf-sup interval [A,B] such that A and B are
floating-point numbers and [a,b] \subset [A,B]. Likewise there is (I
believe) a tightest-possible Level 2 mid-rad interval (M;R) such that M and
R are floating-point numbers and (m;r) \subset (M;R). So everything is fine,
just that if [A,B] and (M;R) are both mapped _exactly_ back to Level 1, it
will not necissarily be the same Level 1 interval. HOWEVER, both will be
guaranteed to be enclosures of the original Level 1 interval [a,b].
I don't see this should be a problem, as I don't expect any user or vendor
mixing inf-sup and mid-rad in a computation would expect otherwise. In fact,
vendors and users will probably for the most part try to do as much of a
calculation as possible in one interval type or the other, minimizing
conversions between the two.
However I apologize for not being able to be more specific yet, if none of
this makes too much sense. This is all a bit new, and I'm still absorbing.
So although I may or may not eventually be proved wrong about this
intuition, my general impression is that it will probably work (i.e., no
compromise to "tightest possible subset" would be necessary). In any case,
its worth further study and investigation, I think.
Nate
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