IMPROVING THE NUMERICAL STABILITY OF FAST MATRIX MULTIPLICATION

被引:20
作者
Ballard, Grey [1 ,2 ]
Benson, Austin R. [3 ]
Druinsky, Alex [4 ]
Lipshitz, Benjamin
Schwartz, Oded [5 ]
机构
[1] Sandia Natl Labs, Livermore, CA 94550 USA
[2] Wake Forest Univ, Dept Comp Sci, Winston Salem, NC 27109 USA
[3] Stanford Univ, Inst Computat & Math Engn, Stanford, CA 94305 USA
[4] Lawrence Berkeley Natl Lab, Berkeley, CA 94720 USA
[5] Hebrew Univ Jerusalem, Sch Comp Sci & Engn, IL-9190416 Jerusalem, Israel
基金
以色列科学基金会;
关键词
practical fast matrix multiplication; error bounds; diagonal scaling; PRACTICAL ALGORITHMS; COMPLEXITY;
D O I
10.1137/15M1032168
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Fast algorithms for matrix multiplication, namely those that perform asymptotically fewer scalar operations than the classical algorithm, have been considered primarily of theoretical interest. Apart from Strassen's original algorithm, few fast algorithms have been efficiently implemented or used in practical applications. However, there exist many practical alternatives to Strassen's algorithm with varying performance and numerical properties. Fast algorithms are known to be numerically stable, but because their error bounds are slightly weaker than the classical algorithm, they are not used even in cases where they provide a performance benefit. We argue in this paper that the numerical sacrifice of fast algorithms, particularly for the typical use cases of practical algorithms, is not prohibitive, and we explore ways to improve the accuracy both theoretically and empirically. The numerical accuracy of fast matrix multiplication depends on properties of the algorithm and of the input matrices, and we consider both contributions independently. We generalize and tighten previous error analyses of fast algorithms and compare their properties. We discuss algorithmic techniques for improving the error guarantees from two perspectives: manipulating the algorithms, and reducing input anomalies by various forms of diagonal scaling. Finally, we benchmark performance and demonstrate our improved numerical accuracy.
引用
收藏
页码:1382 / 1418
页数:37
相关论文
共 26 条
  • [1] Ballard G., 2012, P 24 ACM S PAR ALG A, P193
  • [2] Ballard G, 2011, SPAA 11: PROCEEDINGS OF THE TWENTY-THIRD ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, P1
  • [3] Benson AR, 2015, ACM SIGPLAN NOTICES, V50, P42, DOI [10.1145/2858788.2688513, 10.1145/2688500.2688513]
  • [4] STABILITY OF FAST ALGORITHMS FOR MATRIX MULTIPLICATION
    BINI, D
    LOTTI, G
    [J]. NUMERISCHE MATHEMATIK, 1980, 36 (01) : 63 - 72
  • [5] On the complexity of the multiplication of matrices of small formats
    Bläser, M
    [J]. JOURNAL OF COMPLEXITY, 2003, 19 (01) : 43 - 60
  • [6] Brent RichardP., 1970, ALGORITHMS MATRIX MU
  • [8] Castrapel R.R., 2007, U.S. Patent, Patent No. [7209939B2, 7209939]
  • [9] D'Alberto Paolo., 2014, Advances in Linear Algebra Matrix Theory, V4, P9
  • [10] Z3: An efficient SMT solver
    de Moura, Leonardo
    Bjorner, Nikolaj
    [J]. TOOLS AND ALGORITHMS FOR THE CONSTRUCTION AND ANALYSIS OF SYSTEMS, 2008, 4963 : 337 - 340