Fast and Stable Arbitrary Precision Approximate Matrix Multiplication

DOI10.48550/arXiv.2610.13905MaRDI QIDQ7394766arXivFDO

Authors Ioana Dumitriu, Olga Holtz, Yoav Moran, Ryan Schneider, Oded Schwartz, Shuncheng Yuan, Abraham Hsu, Nicholas Liskij

Publication date 9 October 2026

Published in arXiv

Tldr We introduce novel results on Arbitrary Precision Approximate (APA) matrix multiplication algorithms, including a new search algorithm and the use of alternative bases to minimize additions. We improve existing upper bounds on border rank for $\langle 2,4,5 \rangle$ matrix multiplication and prove stability properties of an APA scheme from Bini [Calcolo 1980].

Full work available at URL https://doi.org/10.48550/arXiv.2610.13905

arXiv classification

math.NA

Cites work

• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• A bilinear algorithm of length \(22\) for approximate multiplication of \(2\times 7\) and \(7\times 2\) matrices
• Accuracy and Stability of Numerical Algorithms
• Adaptive flip graph algorithm for matrix multiplication
• Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
• Discovering faster matrix multiplication algorithms with reinforcement learning
• Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
• Error analysis of the Björck-Pereyra algorithms for solving Vandermonde systems
• Fast linear algebra is stable
• Fast matrix multiplication is stable
• Finding complex-valued solutions of brent equations using nonlinear least squares
• Flip Graphs for Matrix Multiplication
• Flip graphs with symmetry and new matrix multiplication schemes
• Gaussian elimination is not optimal
• Generalized Pseudospectral Shattering and Inverse-Free Matrix Pencil Diagonalization
• How to grade the accuracy of the BLAS
• Improving and estimating the accuracy of Strassen's algorithm
• Improving the numerical stability of fast matrix multiplication
• Matrix multiplication, a little faster
• On Minimizing the Number of Multiplications Necessary for Matrix Multiplication
• On practical algorithms for accelerated matrix multiplication
• On the arithmetic complexity of Strassen-like matrix multiplications
• On varieties of optimal algorithms for the computation of bilinear mappings. I. The isotropy group of a bilinear mapping
• Optimization techniques for small matrix multiplication
• Partial and Total Matrix Multiplication
• Pebbling Game and Alternative Basis for High Performance Matrix Multiplication
• Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time
• Relations between exact and approximate bilinear algorithms. Applications
• Semi-analytical solution of Brent equations
• Semisimple Representations of Quivers
• Sharp Effective Nullstellensatz
• Stability of fast algorithms for matrix multiplication
• Tensor Decompositions and Applications
• The Approximate Bilinear Algorithm of Length 46 for Multiplication of 4 x 4 Matrices
• The bilinear complexity and practical algorithms for matrix multiplication
• Towards a theory of non-commutative optimization: geodesic 1st and 2nd order methods for moment maps and polytopes
• Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
• Towards automated generation of fast and accurate algorithms for recursive matrix multiplication
• Towards Practical Fast Matrix Multiplication based on Trilinear Aggregation
• Trilinear aggregating with implicit canceling for a new acceleration of matrix multiplication

This page was built for publication: Fast and Stable Arbitrary Precision Approximate Matrix Multiplication

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