Improving the numerical stability of fast matrix multiplication

DOI10.1137/15M1032168MaRDI QIDQ2827068zbMATH OpenFDO

Authors Grey Ballard, Austin R. Benson, Alex Druinsky, Benjamin Lipshitz, Oded Schwartz

Publication date 12 October 2016

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.00687

zbMATH Keywords

diagonal scalingerror boundspractical fast matrix multiplication

Mathematics Subject Classification ID

Numerical computation of matrix norms, conditioning, scaling (65F35) Roundoff error (65G50)

Abstract: 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.

Recommendations

• Improving and estimating the accuracy of Strassen's algorithm
• Fast matrix multiplication is stable
• Error-free transformations of matrix multiplication by using fast routines of matrix multiplication and its applications
• Fast linear algebra is stable
• On practical algorithms for accelerated matrix multiplication

Cites work

• A practical algorithm for faster matrix multiplication
• Accuracy and Stability of Numerical Algorithms
• Computational Complexity and Numerical Stability
• Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity
• Fast linear algebra is stable
• Fast matrix multiplication is stable
• Gaussian elimination is not optimal
• Graph expansion analysis for communication costs of fast rectangular matrix multiplication
• Graph expansion and communication costs of fast matrix multiplication
• Improving and estimating the accuracy of Strassen's algorithm
• New lower bounds for the rank of matrix multiplication
• Noncommutative Bilinear Algorithms for 3 \times 3 Matrix Multiplication
• On practical algorithms for accelerated matrix multiplication
• On the complexity of the multiplication of matrices of small formats
• Powers of tensors and fast matrix multiplication
• Stability of fast algorithms for matrix multiplication
• The aggregation and cancellation techniques as a practical tool for faster matrix multiplication
• The bilinear complexity and practical algorithms for matrix multiplication
• The vec-permutation matrix, the vec operator and Kronecker products: a review

Cited in

(16)

• Equivalent polyadic decompositions of matrix multiplication tensors
• Improvement of error-free splitting for accurate matrix multiplication
• Fast matrix multiplication and its algebraic neighbourhood
• Discovering faster matrix multiplication algorithms with reinforcement learning
• scientific article; zbMATH DE number 5058817 (Why is no real title available?)
• Strassen's Algorithm for Tensor Contraction
• Matrix Multiplication in Multiword Arithmetic: Error Analysis and Application to GPU Tensor Cores
• Pebbling Game and Alternative Basis for High Performance Matrix Multiplication
• Numerical stability and tensor nuclear norm
• Extension of accurate numerical algorithms for matrix multiplication based on error-free transformation
• Towards automated generation of fast and accurate algorithms for recursive matrix multiplication
• Stability improvements for fast matrix multiplication
• Strassen's algorithm is not optimally accurate
• Alternative basis matrix multiplication is fast and \(\mathrm{stable}^\dag\)
• How to grade the accuracy of the BLAS
• Fast matrix multiplication is stable

Describes a project that uses

Uses Software

• z3
• mctoolbox

This page was built for publication: Improving the numerical stability of fast matrix multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2827068)