Fast and Stable Arbitrary Precision Approximate Matrix Multiplication
Abstract
We present several new and surprising results on the theory and practice of Arbitrary Precision Approximate (APA) matrix multiplication, which refers to algorithms that output merely approximations to matrix multiplication even in exact arithmetic. While APA algorithms have been around for nearly half a century, and despite the fact that they have potentially lower (asymptotic) cost than many fast exact matrix multiplication schemes, they have not been studied as closely, to the extent that relatively little is known about their numerical properties. In this paper, we shine a spotlight on these algorithms by presenting three important results. First, we provide a new search algorithm for APA routines that is easy to use, automatically generates encoding matrices with functional entries, and can match or beat the best known APA algorithms for several sizes. In particular, we improve the upper bound on the border rank of ⟨ 2,4,5 ⟩ matrix multiplication. Second, we combine this insight with alternative bases to minimize the number of additions in an APA algorithm, thereby improving its leading coefficient. Finally, we prove the same kind of stability that characterizes fast exact matrix multiplication for an algorithm of Bini [Calcolo 1980] that computes an exact product of two matrices using a modified APA scheme (with or without alternative bases).
Related
- Approximate Matrix Multiplication through Joint Leverage Score Sampling
- Ozaki Scheme II Is Fast on CPUs Too: Multiple-Precision Matrix Multiplication on Intel AMX-INT8 and Arm SVE2-i8mm
- Unbiased Low-Rank Approximation for Repeated Matrix-Vector Multiplication: Stability and Optimal Sampling
- Tensor Degenerations for Matrix Multiplication
- Bi-Oriented Interlaced Matrix Multiplication and an Operator Factorisation of the Quantum Harmonic Oscillator
BibTeX
@misc{dumitriu2026fast,
title = {{Fast and Stable Arbitrary Precision Approximate Matrix Multiplication}},
author = {Ioana Dumitriu and Olga Holtz and Abraham Hsu and Nicholas Liskij and Yoav Moran and Ryan Schneider and Oded Schwartz and Shuncheng Yuan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13905},
eprint = {2610.13905},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13905},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Fast and Stable Arbitrary Precision Approximate Matrix Multiplication
AU - Ioana Dumitriu
AU - Olga Holtz
AU - Abraham Hsu
AU - Nicholas Liskij
AU - Yoav Moran
AU - Ryan Schneider
AU - Oded Schwartz
AU - Shuncheng Yuan
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13905
UR - https://arxiv.org/abs/2610.13905
AB - We present several new and surprising results on the theory and practice of Arbitrary Precision Approximate (APA) matrix multiplication, which refers to algorithms that output merely approximations to matrix multiplication even in exact arithmetic. While APA algorithms have been around for nearly half a century, and despite the fact that they have potentially lower (asymptotic) cost than many fast exact matrix multiplication schemes, they have not been studied as closely, to the extent that relatively little is known about their numerical properties. In this paper, we shine a spotlight on these algorithms by presenting three important results. First, we provide a new search algorithm for APA routines that is easy to use, automatically generates encoding matrices with functional entries, and can match or beat the best known APA algorithms for several sizes. In particular, we improve the upper bound on the border rank of ⟨ 2,4,5 ⟩ matrix multiplication. Second, we combine this insight with alternative bases to minimize the number of additions in an APA algorithm, thereby improving its leading coefficient. Finally, we prove the same kind of stability that characterizes fast exact matrix multiplication for an algorithm of Bini [Calcolo 1980] that computes an exact product of two matrices using a modified APA scheme (with or without alternative bases).
ER -