RE: cancelation
If anyone is interested, we had a general (and rather simple) proof that
this "cancelation" is only possible with intervals but not with other
sets:
Olga Kosheleva and Vladik Kreinovich, "Only Intervals
Preserve the Invertibility of Arithmetic Operations",
Reliable Computing, 1999, Vol. 5, No. 4, pp. 385-394.
-----Original Message-----
From: stds-1788@xxxxxxxx [mailto:stds-1788@xxxxxxxx] On Behalf Of Ralph
Baker Kearfott
Sent: Thursday, September 10, 2009 11:37 AM
To: Dan Zuras Intervals
Cc: stds-1788@xxxxxxxxxxxxxxxxx
Subject: Re: Request for motion [Fwd: Input from IFIP WG 2.5 to IEEE
Interval Standards Working Group]
Dan (and Chenyi, if I may step in),
Cancellation is when you create a sum \sum x_i and need \sum_{i\ne j}
x_i. You
then subtract x_i from the sum, but you do it in such a way that there
isn't overestimation,
that is, we get, to within roundout error, the same interval as we would
have if
we had omitted x_j from the original sum. This is useful, e.g. in
Gauss--Seidel iteration.
For example, cancellation produces x \cancelminus x = [0,0]
The operation is subtraction, where it is assumed that, in the resulting
interval,
every point value in the first operand must be equal to every point
value in the
second operand in forming the set of all possible results. (That is, we
assume dependency.)
Of course, there's a very simple operational definition in terms of the
end points :-)
How did I do with the explanation, Chenyi?
Baker
Dan Zuras Intervals wrote:
>> Date: Thu, 10 Sep 2009 10:47:43 -0500
>> From: "Chenyi Hu" <chu@xxxxxxx>
>> To: "R. Baker Kearfott" <rbk@xxxxxxxxxxxxx>,
>> "Dan Zuras Intervals" <intervals08@xxxxxxxxxxxxxx>
>> Cc: "James Demmel" <demmel@xxxxxxxxxxxxxxx>,
>> "Nathalie Revol" <Nathalie.Revol@xxxxxxxxxxx>,
>> <stds-1788@xxxxxxxxxxxxxxxxx>,
>> "Ronald Boisvert" <boisvert@xxxxxxxx>,
>> "Arnold Neumaier" <Arnold.Neumaier@xxxxxxxxxxxx>
>> Subject: Re: Request for motion [Fwd: Input from IFIP WG 2.5 to IEEE
>> Interval Standards Working Group]
>>
>> Dan, et al,
>>
>> Just for your information, about a decade ago, Jim and I were on the
>> BLAST working group led by Jack. That group tried to establish an
Interval
>> BLAS standard including BLAS-1, -2, and -3. The final document is
available
>> at http://www.netlib.org/blas/blast-forum/chapter5.pdf. Also, my
former
>> graduate student Michael Nooner made a reference implementation which
is
>> available at http://www.cs.uca.edu/interval/intbox/ with
documentation. We
>> further described the design and implementation as chapter 10 in the
book
>> "Knowledge Processing with Interval and Soft Computing" published by
>> Springer last year. Since we did not have a standard on interval
computing,
>> the Interval BLAS was listed under Journal of Development in the
final
>> document of BLAST.
>>
>> Regards,
>>
>> Chenyi
>>
>>
>
> Cool.
>
> I notice a basic interval operation called 'cancellation'
> that I haven't heard others speak of. At least not by
> that name. Can you give me a brief explanation of what
> its used for?
>
> Other than issues involving the increment & length integers
> having values <=0 & the occasional mention of empty on
> intersection, I see no mention of exceptional behavior.
> That is, the behavior of these routines when presented
> with exceptional interval elements.
>
> Is this because exceptional interval behavior is not
> considered or that such behavior is described elsewhere?
>
> I ask because, as a standards body, we spend an inordinate
> amount of time concerning ourselves with such things. Far
> more than our users need to. And I am curious if this work
> has given you any insights into exceptional behavior that
> would help us in designing the standard.
>
> Operations on vectors & matrices with elements such as NaI,
> empty, or even an interval element of infinite width could
> affect the whole result, just a column or row, or perhaps
> only an element or two.
>
> Are such things handled gracefully or just punted?
>
> What would you advise US to do?
>
> Could your work form the basis for an interval BLAS in 1788
> or should we use it as a starting point for something else?
>
> Thanks,
>
> Dan
>
>