Re: Motion9 ExactDot Product
Ulrich Kulisch 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.
There was some response: I copy a few sentences of my response mail
(dated October 20):
The IFIP Working Group letter requests an "exact" dot product as support
for long interval arithmetic (for details see [6] or [9]). Long interval
arihtmetic opens a new area of applications for interval arithmetic. I
give a few examples:
The Krawczyk operator frequently is used to compute a verified enclosure
for the solution of a system of linear equations. But for ill
conditioned problems (take the Hilbert matrices of dimension larger than
11) the Krawczyk operator fails to find the solution.
In such cases a more powerful operator (called the Rump operator in [9])
solves the problem. In its extended form the Rump operator can be used
to compute a verified solution even for extemely ill conditioned
problems, see [11]. The Rump operator uses the "exact" dot product.
But all this can be done as efficiently with the optimally rounded dot
product, since all that matters is that sufficiently many significant
digits are produced.
This is the reason, I think, why Siegfried Rump got interested in
algorithms for the latter. In any case, I'd like to see his comment
on this issue.
Another very nice example is given in [7], an iteration with the
logistic equation. Double precision floaint-point or interval arithmetic
totally fail (no correct digit) after 30 iterations while long interval
arithmetic after 2790 iterations still computes correct digits of a
guaranteed enclosure. Long interval arithmetic allows computing highly
accurate bounds for real arithmetic expressions.
Rump published work on how to get least significant bit accuracy for
arbitrary arithmetic expressions (and this includes 2790 iterations of
thee logistic equation) using fixed-point iteration, and this only
depends on getting the dot product to a fixed relative accuracy;
no use is made there of the exact dot product beyond this property.
Arnold Neumaier