Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

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