P1788/M0014.01: 6.1_and_6.2 (compatibility with multi-precision)
Dan, Michel, P1788
So far we seem to have these conclusions about multi-precision:
1. (optimistic) Paul Zimmermann says that the MPFI system is based on a sequence of binary_N formats for (in principle) any N>1. Assuming each of these is of the required level 2 kind, this seems to make MPFI fit into the level 3 framework of 6.1, 6.2.
2. (optimistic) For multi-precision systems using (mid,del1,del2) format or the (x0,ex,ee) format mentioned in Vienna 1.6 para 3, what Dan and Michel say persuades me that for *narrow* intervals, the systems either fit into the required "sequence of formats" framework, or can be coerced to it by modest outward rounding with insignificant loss of accuracy.
3. (dubious) Intervals like Dan's example, say xx = [10^-N,10^N] for "large" N. I don't think the (x0,ex,ee) form has *any* satisfactory exact representation. So one would have to round out the 10^-N to zero. Presumably there are restrictions on the (mid,del1,del2) form (for storage economy etc.) that make it similarly unsatisfactory for this kind of interval. Dan?
John
On 29 Apr 2010, at 16:23, Dan Zuras Intervals wrote:
>> From: John Pryce <prycejd1@xxxxxxxxxxxxx>
>> Date: Thu, 29 Apr 2010 14:47:46 +0100
>> Cc: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
>> To: Michel Hack <hack@xxxxxxxxxxxxxx>
>>
>> Michel, Dan
>> On 27 Apr 2010, at 20:32, Michel Hack wrote:
>>>> On the other hand, mid-rad intervals of the form
>>>> veryLarge +/- verySmall exist even in precisions
>>>> substantially less precise than verySmall/veryLarge.
>>>> These have no counterpart in the inf-sup world.
>>>
>>> That is indeed a problem. One would need something like
>>> the triplex representation described in the Vienna Proposal.
>>>
>>> Can the (mid,del1,del2) format be restricted so as to
>>> preserve interconvertibitity? Clearly, the requirement
>>> would be that mid-del1 and mid+del2 be representable,
>>> which means that del1 and del2 must (a) not be too small,
>>> and (b) have limited resolution, i.e. sufficiently many
>>> trailing zeros. It is unlikely that the result of a
>>> computation would satisfy (b) -- so I think the answer
>>> here is NO.
>
> Actually, I think the answer here is 'possibly'.
>
> That is, while the result of any given operation
> in mid-rad form might not be exactly convertable
> to an inf-sup form, I believe it can be coerced
> into such a form. Usually by rounding del1 or
> del2 out a bit.
>
> Whether this is desireable or not is another question.
>
>>
>> Here I would like to know more of how the multi-precision (MP)
>> algorithms use these representations. For both the (mid,del1,del2)
>> form and the triple form (x0,ex,ee) mentioned by Vienna, where
>> x0 is a base point,
>> ex is an exponent (typically large negative),
>> ee is the scaled offset, a standard interval,
>> and it represents the (exact) interval
>> xx = x0 + B^ex * ee where B is the base of the arithmetic.
>
> I don't find this in Vienna (part 2) but I take your point.
>
>>
>> Take the Vienna form -- the other form is very similar.
>> Q:
>> (i) Assume we are talking "small errors". Is the map
>> phi: e -> x = x0 + B^ex * e
>> a sort of local coordinate system laid down and used by a number
>> of intervals xx_i, so that they only differ in their scaled offsets ee_i ?
>> (ii) Or does each xx have its own x0 and ex as well as ee?
>>
>> Maybe some algorithms do (i), others do (ii).
>> In case (i), there is no reason to expect x0 to be within all,
>> or indeed any, of the xx_i. And x0 may be of much coarser
>> precision than the xx_i: a "coarse tick mark" on an axis,
>> w.r.t. which the "fine tick marks" are measured locally.
>> In case (ii), I think it makes sense for x0 to be inside xx,
>> and its precision (=roundoff unit) u to be close to the
>> precision with which xx is measured. A canonical case of this
>> might to scale things so u = B^ex, and one ULP in each of the
>> bounds of ee is 1, (maybe 2 or 1/2?), so basically we're
>> measuring xx in ULPs of x0 on either side of x0.
>>
>> Basically there is no point in giving the offsets from x0 (or
>> mid) a finer resolution than what we choose as "current ULP"
>> around x0 (or mid). This is easily achieved by discarding
>> precision from the bounds of ee (or from del1 and del2) by
>> suitable outward rounding.
>> - This loses negligible accuracy, about one current ULP on average I suppose.
>> - It is cheap, and probably could be organised to come for free.
>> - Once it is done one has basically fitted the MP scheme into
>> a sequence of infsup formats, as the theoretical model would like.
>>
>> Or have I got the wrong end of the stick?
>
> No, I think you've got it. At least as I understand it.
>
>>
>>> Can any (inf,sup) be converted to (mid,del1,del2) where
>>> the middle is (inf+sup)/2 rounded either way, and del1
>>> and del2 are such that we have an exact correspondence?
>>> Only at the cost of variable and excessive precision, if
>>> inf and sup are of vastly different magnitude. Suppose
>>> inf=1e-100 and sup=1e+100. Then mid would be 0.5e+100,
>>> and del1 and del2 would have to be the same, except just
>>> a very tiny bit smaller: no go.
>>>
>>> Is there ANY midrad-style representation that could be
>>> exactly interconvertible with infsup?
>
> I have no problem with minor roundoff error on
> conversion from inf-sup to mid-rad. If you need to
> do it exactly you can always do the above problem
> exactly by taking [1e-100,1e+100] to (0.0,1e-100,1e+100)
> so long as you don't mind the mid not being in the
> interval & the rad is of sufficient precision.
>
>>
>> I may well be totally misunderstanding, but it seems to me this
>> is unnecessary and over-complicated.
>>
>> Cheers
>>
>> John
>>
>
> I think it is necessary if we are to maintain some
> ability to verify things from one implementation to
> the next.
>
> In particular, from Vienna page 14, "Two intervals are
> regarded as equal if the values of the lower bounds
> agree and the values of the upper bounds agree...".
>
> But if there is a roundoff error in extracting those
> bounds we will have intervals that look the same to
> the user but behave different in calculations.
>
> There is a technical term for this: It would be bad.
>
> Still, something must be done to save the ability to
> use mid-rad when it is needed.
>
> My (admittedly light) reading of the literature tells
> me that the mid-rad form is favored in two applications:
> very high precision with very narrow intervals & large
> linear algebra applications. Do I have that right?
>
> For high precision, the advantage is merely a constant
> factor around 2. So let me ignore that for now as
> being something that can be lived with.
>
> But in the linear algebra case, the advantage can be
> of an order faster. In extreme cases, solvable in
> polynomial time for tight results whereas the inf-sup
> form can take exponential time.
>
> If that is the case, can we consider the proper domain
> of mid-rad applications to be canned packages that take
> inf-sup on input, do their work in mid-rad, & return
> the results in inf-sup again? As a canned package, all
> of the intermediate results are out of sight so the
> problem of exact interconvertability does not arise.
>
> But, let me float another wild hair (as well as mixed
> metaphor) balloon: It occurs to me that pretty much
> any large linear algebra problem in inf-sup form is
> equivalent to a feasibility problem & thus solvable
> with simplex methods. And while simplex is theoretically
> exponential, most packages are typically both polynomial
> & very fast. Can these problems be cast in this form
> & solved this way?
>
> I realize that considering the input intervals as
> problem constraints means that some of these linear
> algebra problem are non-linear in those constraints
> so this may not work in all cases.
>
> On another mildly related topic, if you give Vienna a
> scan today I think you will find it is quite out of
> date considering the discussions we've had in the past
> 16 months. Perhaps we should no longer consider it
> a reference document. Perhaps we should work off John's
> version 2.2 (& later) document from now on. Just a
> thought.
>
>
> Dan
John Pryce
46 Ponting Street
Swindon SN1 2BW
j.d.pryce@xxxxxxxxxxxx