SOME HIGHLY ACCURATE BASIC LINEAR ALGEBRA SUBROUTINES

Abstract

<p>In the computation of the sum of many floating-point numbers Xi (i = 1,2, ... n-1,n), the method S = (( ... ((Xi +X2)+X3)+ ... +Xn-1)+Xn) is called the Ordinary Recursive Summation (ORS) algorithm. Since significant digits might be discarded when the partial sums are rounded, the results are rarely correct. In 1969, Knuth [IJ proposed a simple algorithm AddTwo for transforming a pair of floating-point numbers (a, b) into a new pair (x, y) with non-overlapping mantissas and satisfying x = fl(a + b) and a + b = x + y, regardless of the magnitude of a and b, where x is the floating-point sum of a and b, while y is the roundoff error. We call an algorithm with such property an error-free transformation. Such transformations are at the center of the interest of this thesis. Extending the principle of AddTwo to n, summands is called distillation by Kahan. Since then, many distillation algorithms have appeared to improve the accuracy of summation. Among them, there are three accurate summation algorithms SumK, iFastSum and HybridSum, which are particularly appropriate for ill-conditioned data, where ORS fails due to the accumulation of rounding error and severe cancellation. In this thesis, we present the accurate summation algorithms with their properties, and then apply them to improve the accuracy of the LAPACK subroutines DDOT and DGEMV.</p>