Re: Motion P1788/M0009.01_ExactDotProduct
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 primary advantage of Motion 9 is that it proposes a primitive, namely
CompleteMultiplyAndAccumulate, that permits exact dot products to be
computed piecemeal. It also supports parallel evaluation, where the job
of computing a large dot product is parcelled out to different threads.
(This is why the CompleteAddition primitive is also required, namely to
combine the pieces.)
(The motion uses the name completeMultiplyAdd -- but I think that
Accumulate is a better description of the function than Add.)
Michel.
---Sent: 2009-10-30 18:06:47 UTC