Improving and estimating the accuracy of Strassen's algorithm
Subject Classification (1991): 65F30, 65F35, 65G05
Springer Online Journal Archives 1860-2000
Abstract. Fast matrix multiplication algorithms of Strassen and Winograd are known to have weaker numerical accuracy than usual (inner product) multiplication. In this paper, we show that scaling usually improves accuracy when operands have elements of widely varying magnitude. We also propose estimators for numerical errors, based on samples of the result. All these estimators can be computed in $O(n^2)$ operations. Experiments prove the effectiveness of the scaling idea and of the absolute error estimator.
Type of Medium: