Source-linked AI summary
Rectangular matrix multiplication from shared-leg entropy
Przemyslaw Uznanski
TL;DR
Rectangular matrix-multiplication exponents depend on product shape, and square-matrix results do not settle every rectangular case. The note extends shared-leg analysis using oriented sectors and coupled-profile bounds, proving exponent two through k = 1/2 and a further rectangular upper bound.
Problem
Rectangular exponents depend on product shape, and an improvement for square matrices need not yield a comparable improvement for every rectangular shape.
Source: §1 · p. 1Method
The analysis retains sector orientation, averages two legs, and uses homogenized auxiliary profiles to derive a parabolic constraint on tensor-character parameters.
Source: §1 · p. 2Results
Theorem 1.1 gives exponent two for inner dimension up to n^0.5 and, for k ≥1, an upper bound within 1/(4k) of the input-size lower bound 1 + k.
Source: §1 · p. 2Takeaways & Limitations
The bound gives O(n^2) time for multiplying two n × n matrices with at most n^1.25 nonzero entries each.
Source: §7 · p. 10The comparison constants in the profile analysis may depend on the fixed tensor character.
Source: §3 · p. 6
Abstract
from arXiv · showhide
In this note, we extend the analysis underlying a recent matrix-multiplication result by OpenAI to rectangular products and prove that $\omega(1,k,1)\le 2$ for $0\le k\le \frac{1}{2}$ and $\omega(1,k,1)\le 1+k+\frac{1}{4k}$ for $k\ge \frac{1}{2}$. In particular, $\omega(1,\frac{1}{2},1)=2$ and the dual exponent satisfies $\alpha\ge \frac{1}{2}$. We use the shared-leg entropy inequality and polynomial-multiplication degenerations from that work, retaining two-leg symmetry and the orientation of each sector. Logarithmic averaging produces homogeneous auxiliary profiles. Their powered versions have a common asymptotic slope, and bounding their intercepts gives the spectral constraint $b\le 4a(1-a)$. This yields the rectangular curve by tensor-spectrum duality. 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.
1 Introduction
Rectangular exponents vary with product shape, so a square-matrix bound does not determine every rectangular case. This note extends the analysis and establishes an exponent-two regime through inner dimension n^0.5.
1 Introduction
- Complexity bounds suppress a +o(1) exponent term, and all shape parameters are fixed.Source: §1 · p. 1
- Theorem 1.1 gives exponent two for inner dimension up to n^0.5 and, for k ≥1, an upper bound within 1/(4k) of the input-size lower bound 1 + k.Source: §1 · p. 2
- The proof bounds tensor-character dot-product parameters by averaging two legs to (a0, a0, b0) and proving b0 ≤ 4a0(1 − a0).Source: §1 · p. 2
- The new analysis simultaneously homogenizes two profiles and bounds their common asymptotic slope and intercepts; the tensor constructions and application algorithms are inherited from prior work.Source: §1 · p. 2
2 Tensor characters and polynomial multiplication
The section combines tensor-character bounds with oriented polynomial-multiplication degenerations, then uses partial symmetrization and discrete profiles to constrain rectangular parameters.
2 Tensor characters and polynomial multiplication
- Shared-leg entropy inequalities and oriented polynomial-multiplication degenerations provide matched sectors, including tensors of rank r + s − 1, for bounding tensor characters.Source: §2 · p. 3
2.1 Partial symmetrization
- Averaging across the X/Y interchange yields a positive, multiplicative, restriction-monotone M with parameters (a0, a0, b0); M need not be additive.Source: §2.1 · p. 4
2.2 Discrete profiles
- The oriented profiles are coordinatewise nondecreasing and their powered forms satisfy coordinate-specific concavity and tripling inequalities; zero parameters make the corresponding profile constant.Source: §2.2 · p. 4
3 Homogeneous auxiliary profiles
The section constructs homogeneous auxiliary profiles by logarithmic averaging and shows that they retain symmetry, monotonicity, powered concavity, and continuum tripling inequalities.
3 Homogeneous auxiliary profiles
- Logarithmic homogenization constructs the auxiliary profiles from discrete profile values while preserving powered concavity and tripling.Rounding and interpolation errors vanish as the averaging horizon tends to infinity, yielding continuum tripling inequalities.Source: §3 · pp. 5–6
- The resulting positive, locally Lipschitz profiles are homogeneous of degree δ, with V(1,1)=1; V is symmetric and both profiles are nondecreasing.Their powered concavities and tripling inequalities are inherited in the limit.Source: §3 · p. 5
- A common normalization and a diagonal subsequence yield locally uniform limits of both profiles.The construction uses expanding compact rectangles and lets the averaging horizon tend to infinity.Source: §3 · pp. 5–6
- The comparison constants in these arguments may depend on the fixed character.Source: §3 · p. 6
4 Common slopes and bounded intercepts
Powered profiles P and Q share a positive asymptotic slope and have bounded residual intercepts; these bounds yield the parabolic constraint on the character parameters.
4 Common slopes and bounded intercepts
- P and Q share a positive slope L, and their finite, nonnegative intercepts satisfy CP+CQ≤L, CP≥1−L, CQ≤2L−1, and L≤1.Source: §4 · p. 7
- Subtracting Ls makes P(s)−Ls and Q(s)−Ls nondecreasing, with finite limits whose sum is at most L.Since P(1)=1, its residual limit is at least 1−L, which bounds the other limit by 2L−1.Source: §4 · p. 7
- The common-slope and intercept bounds imply the parabolic parameter constraint b≤4a(1−a).Source: §4 · p. 8
5 The rectangular exponent curve
The character constraint yields a rectangular matrix-multiplication exponent curve through optimization, with equality in the small-inner-dimension range and algorithms realizing the bound.
5 The rectangular exponent curve
- Every character satisfies b0≤4a0(1−a0), where a0=(pX+pY)/2 and b0=pZ.The rectangular objective is 2a0+kb0.Source: §5 · p. 8
- For k≥1/2, the rectangular exponent bound is 1+k+1/(4k; for 0≤k≤1/2, it is 2.The optimization is over the character-constraint region and does not require a character attaining the optimizer.Source: §5 · p. 8
- Tensor-power rank decompositions turn the character bound into algorithms, and blocking extends the result to real k.Padding from fixed base sizes to arbitrary n costs a constant factor for each fixed algorithm.Source: §5 · p. 8
- For 0≤k≤1/2, the bound is exact: the output flattening gives ω(k)≥2, matching the upper bound.Source: §5 · p. 8
6 Three unequal dimensions
Permuting the parabolic character constraint gives bounds for matrix multiplication with three unequal dimensions, followed by an elementary optimization over the character objective.
6 Three unequal dimensions
- Applying the character constraint after each leg permutation supplies bounds for general ω(a,b,c).The proof reorders the objective as ap1+bp2+cp3 and uses S=p1+p2+p3 to optimize under those constraints.Source: §6 · p. 9
- For b≥2c, the exponent bound is attained by the size lower bound.Source: §6 · p. 9
- The complementary optimization branch for b<2c has its maximum at d=(a−c)/(a+c−b).The two branch maxima yield the stated bound by tensor-spectrum duality.Source: §6 · p. 9
7 Applications
Theorem 1.1 and Corollary 6.1 are applied through standard rectangular-multiplication balances to graph and matrix problems. The applications include shortest paths, dynamic matrix operations, sparse multiplication, and witness finding.
1. One lowest common ancestor per pair in a DAG
- The one-lowest-common-ancestor-per-pair DAG application uses Grandoni et al.’s balance ω(x)=3x, giving exponent 1+2x [4].Source: §7 · p. 9
2. Exact all-pairs Hamming distance
- Exact all-pairs Hamming distance over unrestricted alphabets is reduced to dominance products and analyzed at balance ρ=ω(4−ρ) [5, 8].Source: §7 · p. 9
3. The standard unweighted APSP balance
- O(n^2.4999) running time follows from combining the full curve with the deterministic (min,+)-product algorithm and APSP reduction [1]; Zwick’s standard balance gives O(n^2.5).The bounds use arithmetic operations, with graph operations and symbol comparisons also charged.Source: §7 · pp. 9–10
4. Minimum and maximum witnesses
- O(n^2.5) time suffices to find all minimum and maximum witnesses.A witness for entry (i,j) is the least or greatest index k with Aik=Bkj=1.Source: §7 · p. 10
5. Sparse matrix multiplication
- For m≤n^1.25 nonzeros per matrix, the sparse–dense decomposition gives O(n^2) time.The stated running time is O(m^2/n^r + n^ω(r)) for 0≤r≤1.Source: §7 · p. 10
6. Dynamic matrix inverse and reachability
- O(n^1.31125) worst-case time per entry update and query, after O(n^2.25) preprocessing, also applies to directed reachability edge updates with O(1) fixed-pair queries.The dynamic matrix-inverse bounds follow by minimizing the stated tradeoff; reachability uses an associated Monte Carlo reduction.Source: §7 · p. 10