arXiv preprint ·
Rectangular matrix multiplication from polynomial products
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In this note, we extend the matrix-multiplication analysis by OpenAI to rectangular products and prove $ω(1,k,1)\le2$ for $0\le k\le\frac{1}{2}$, and $ω(1,k,1)\le1+k+\frac{1}{4k}$ for $k\ge\frac{1}{2}$. In particular, $ω(1, \frac{1}{2},1)=2$ and the dual exponent satisfies $α\ge\frac{1}{2}$. The proof uses explicit degenerations of convolution tensors, multinomial counting, and Strassen's spectral theorem. An angular constraint on three dot-product parameters gives both the rectangular curve and a bound for $ω(a,b,c)$. As an application, Zwick's algorithm for all-pairs shortest paths in directed unweighted graphs runs in $O(n^{2.5})$ time. Combining the rectangular bound with the $(\min,+)$-product improvement of Alman and Vassilevska Williams further gives $O(n^{2.4999})$ running time.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Generating cyclic pivot Gray codes for well-ordered $k$-degenerate graphs in constant amortized time
Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
Envy-free Allocations with Individual Payments
Tight bounds and output sensitive algorithms for maximal clique enumeration in link streams
Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.