4
$\begingroup$

In John Gustaffson's book The End of Error, he discusses Ulrich Kulisch's exact dot product, which (in double precision) requires a 2100 bit fixed point register which rounds only once after the computation of the dot product is complete.

I have found only one statement about how this instruction can be used in numerical analysis, namely Kulish claims "it is the EDP which makes residual correction effective . . " However, I could not find a reference demonstrating this claim.

What numerical methods would benefit from an exact dot product? And more interestingly, are there algorithms which become stable in the presence of a hardware dot product which are unstable otherwise?

$\endgroup$
5
  • $\begingroup$ I think the classical Gram-Schmidt algorithm is one of them. Except for some simple cases, it is not stable under floating point arithmetic, but the issue can be fixed by reordering the operations -called Modified Gram-Schmidt- (math.stackexchange.com/a/1676362). I don't know many algorithms that fail only due to errors coming from dot products, but it is a source of error and getting rid of a source of error is always good. $\endgroup$ – Abdullah Ali Sivas May 29 at 15:37
  • $\begingroup$ The poster has the sentence "This has a direct and positive influence on all iterative solvers of systems of equations." so this would actually be beneficial for all Krylov subspace methods as an example. $\endgroup$ – Abdullah Ali Sivas May 29 at 15:39
  • 1
    $\begingroup$ I know I am putting a lot of comments and probably I should combine all to an answer; but here are more links that are relevant: blogs.mathworks.com/cleve/2015/02/16/… and blogs.mathworks.com/cleve/2015/03/02/… $\endgroup$ – Abdullah Ali Sivas May 29 at 15:56
  • 1
    $\begingroup$ @AbdullahAliSivas: Nice link! Cleve is doing essentially the same thing in software as Kulisch wanted in hardware. $\endgroup$ – user14717 May 29 at 16:42
  • $\begingroup$ The poster has a very simple example that fails under double precision arithmetic, but is stable under exact dot products: $x_{n+1}=3.75 x_n (1-x_n), x_0 = 0.5$ $\endgroup$ – Charlie S May 30 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.