When the condition number is not high, one can do the naive algorithm for the dot product. Otherwise, one should do the compensated algorithm.
- Let \((s_{1},c_{1})\) be the product of \(a_{1},b_{1}\)
- For all the other entries:
- \((p_{i},\pi_{i})=\) product of \(a_{i},b_{i}\)
- \((s_{i},\sigma_{i})\) is the 2Sum of \(p_{i},s_{i-1}\)
- \(c_{i}=\RN(c_{i-1}+\RN(\pi_{i}+\sigma_{i}))\)
- Return \(\RN(s_{n}+c_{n})\)
All products are either Dekker of Fast2MultFMA
The basic idea is you keep accumulating the “leftovers” of both the sum and the products.
The error of the compensated dot product, for \(\beta=2\) if no underflow or overflow occurs, is:
\begin{equation*}
e\le\mathbf{u}\left|\sum_{i=1}^{n}a_{i}b_{i}\right|+\gamma_{n}^{2}\sum_{i=1}^{n}|a_{i}b_{i}|
\end{equation*}