Re: Motion P1788/M0009.01_ExactDotProduct

[Ulrich Kulisch <Ulrich.Kulisch@xxxxxxxxxxx>]

Arnold Neumaier schrieb:
> Michel Hack wrote:
> > Arnold Neumaier wrote:
> > > I had therefore asked for providing evidence for applications that 
> > > really
> > > need the exact dot product, but this hasn't generated any response.
> >
> > Jim Demmel replied:
> > > Though I have not written this down formally, I think that an algorithm
> > > that is correct for any underlying number of mantissa and exponent bits
> > > must in effect do as much work as sorting (by the exponents).
> >
> > Sorting in order to discover and eliminate cancellations (which is 
> > what the
> > real problem is) assumes that the entire input set is available at once.
>
> The Zhu/Hayes paper quoted by Demmel shows that one can do the 
> computations with a single pass through the data in an online fashion,
> with a storage that only in the worst case takes the length of the 
> accumulator needed for the exact dot product.
The 'single pass' is not needed if you add the products in fixed-point 
arithmetic. Fixed-point addition is simpler (no rounding and no 
normalization) and (in general) faster than floating-point addition. The 
summands can be added in an arbitrary order.

Ulrich Kulisch
> Arnold Neumaier