Simultaneous Matrix Multiplication by Tensor Contraction Aggregation
Abstract
We present an interpretation of the fast matrix multiplication algorithms of Coppersmith and Winograd as aggregations of tensor contractions. This point of view provides a direct connection to older constructions by Pan and to more recent work on bilinear algorithms for symmetric tensor contraction. Further, we provide a simple explicit approach for exact aggregation of tensor contractions, each one yielding an independent matrix-matrix product. These constructions and border rank adaptations thereof do not come close to improving the best known bounds on ω (the matrix multiplication exponent), but provide explicit moderate-size fast matrix multiplication algorithms that achieve a better exponent than Strassen's algorithm and have potential practical value. These finite constructions improve the multiplication-count bounds of the reference algorithms compared here for selected numbers and dimensions of independent square matrix products. In particular, using ⟨ m,m,m⟩ to denote the matrix multiplication tensor for matrices of dimension m, we obtain constructions that give bounds such as the border rank bound underline R (⟨ n2,n2,n2⟩⊕9) ≤ (n+1)6+6(n+1)5, and the exact rank bound R (⟨ n3,n3,n3⟩⊕14)≤ (n+1)9. We quantify the accuracy of such constructions in finite precision, and provide border-rank constructions that reduce cost with limiting retained fractions of accuracy at least 1/2, 1/3, or 1/4 relative to the classical matrix-multiplication approach under the stated error model.
Related
- Tensor Degenerations for Matrix Multiplication
- Low-Latency Coded Tensor--Matrix Multiplication for Distributed Signal Processing Systems
- Approximate Matrix Multiplication through Joint Leverage Score Sampling
- Unbiased Low-Rank Approximation for Repeated Matrix-Vector Multiplication: Stability and Optimal Sampling
- Bi-Oriented Interlaced Matrix Multiplication and an Operator Factorisation of the Quantum Harmonic Oscillator
BibTeX
@misc{solomonik2026simultaneous,
title = {{Simultaneous Matrix Multiplication by Tensor Contraction Aggregation}},
author = {Edgar Solomonik and Markus Bläser},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26563},
eprint = {2610.26563},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26563},
}
RIS
TY - UNPB
TI - Simultaneous Matrix Multiplication by Tensor Contraction Aggregation
AU - Edgar Solomonik
AU - Markus Bläser
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.26563
UR - https://arxiv.org/abs/2610.26563
AB - We present an interpretation of the fast matrix multiplication algorithms of Coppersmith and Winograd as aggregations of tensor contractions. This point of view provides a direct connection to older constructions by Pan and to more recent work on bilinear algorithms for symmetric tensor contraction. Further, we provide a simple explicit approach for exact aggregation of tensor contractions, each one yielding an independent matrix-matrix product. These constructions and border rank adaptations thereof do not come close to improving the best known bounds on ω (the matrix multiplication exponent), but provide explicit moderate-size fast matrix multiplication algorithms that achieve a better exponent than Strassen's algorithm and have potential practical value. These finite constructions improve the multiplication-count bounds of the reference algorithms compared here for selected numbers and dimensions of independent square matrix products. In particular, using ⟨ m,m,m⟩ to denote the matrix multiplication tensor for matrices of dimension m, we obtain constructions that give bounds such as the border rank bound underline R (⟨ n^2,n^2,n^2⟩^⊕9) ≤ (n+1)^6+6(n+1)^5, and the exact rank bound R (⟨ n^3,n^3,n^3⟩^⊕14)≤ (n+1)^9. We quantify the accuracy of such constructions in finite precision, and provide border-rank constructions that reduce cost with limiting retained fractions of accuracy at least 1/2, 1/3, or 1/4 relative to the classical matrix-multiplication approach under the stated error model.
ER -