On the estimation of numerical error bounds in linear algebra based on discrete stochastic arithmetic

摘要

In this paper, a method to estimate error bounds of algorithms in linear algebra is proposed which is independent of the considered algorithm. The method is based on discrete stochastic arithmetic (DSA) which has been introduced to compute the numerical accuracy of algorithms providing scalar values. In order to extend the DSA concept to algorithms in linear algebra, estimations of numerical error bounds for the 2-norm of vectors and angle between subspaces spanned by computed vectors and corresponding true vectors are derived based on DSA in this paper. To show the quality of these estimations, they are applied to the linear algebra library LAPACK providing tighter error bounds compared to the error bounds of the library itself. These error bounds are especially useful for the implementation of algorithms in linear algebra on low precision (e.g. single precision) arithmetic of massive parallel computing systems (GPUs, FPGAs, Cell processors, multi-core processors). In such systems, single precision arithmetic offers a significant higher performance than double precision arithmetic. In order to avoid numerical inaccurate results, a numerical error control is required which can be provided by the given approach. In a similar way, the error bounds are useful in cases where double precision may be not sufficient and have to be extended to quadruple precision.