Lower bounds for matrix multiplication #

Let matMul n : F ^ (n² + n²) → F ^ (n²) be the product C = A B of two n × n matrices over a field F, written in coordinates (MatMul.Defs; matMul_matMulInput). Consider circuits over F, over any signature whose gates have at most two arguments, so with arbitrary functions F × F → F, unary functions and constants as gates; over F = GF(2) these are the circuits over the full binary basis B₂ computing the Boolean matrix product modulo two. Over arbitrary fields K, also consider circuits with polynomial gates of fan-in at most two, and arithmetic circuits of additions, multiplications and free constants (Arithmetic.gateCost). The model is that of MultiOutput.FieldMul and MultiOutput.TotallyRegular: the size counts gates, inputs and output designations are free.

The terminal graph (MatMul.Tripartite). The inputs A i j, B j k and the outputs C i k are the edges of the complete tripartite graph on three copies I, J, K of Fin n. A split S of the wires places d v of the 2 n terminals at each vertex v; the charges R_I, R_J, R_K sum min (d, 2 n - d) over the vertices of each part.

The charge bounds (charges_le_of_matMul_of_totallyRegular, charges_le_add_of_matMul, charges_le_of_matMul_polynomial). Let S be crossed by w forward and backward signals.

Fixing B = B₀ makes the product linear in A, with change δA ↦ δA B₀, block diagonal over the rows i; by the restricted rank-cut bound (card_pow_le_supportedKernel), w is at least the rank of the blocks B₀[A_S(i), C_T(i)] and B₀[A_T(i), C_S(i)], summed over i.
Fixing A = A₀ gives the same over the columns k.
For any Λ, the combination ∑ i k, Λ i k C i k of the outputs is a quadratic form whose Hessian pairs A i j with B j k through Λ i k; by the rank-cut bound for a combination of outputs (blockRank_add_transpose_le_of_sum), w is at least the rank of its cross block, which is block diagonal over the inner index j.

If F has a totally regular n × n matrix (every square submatrix nonsingular), used for B₀, A₀ and Λ, every block has full rank and R_I, R_J, R_K ≤ w; this holds over ZMod q for a prime q ≥ 2 n with the Cauchy matrix cauchyZMod q n, and for polynomial gates over any field K by evaluating over K(t) with the generic Hankel matrix (totallyRegular_genericHankel). Over every finite field, in particular GF(2), a uniformly random n × n matrix has kernel blocks of average size at most twice the ideal size, so a matrix chosen after the split loses at most 4 n: R_I, R_J, R_K ≤ w + 4 n.

One component (mem_component_of_matMul). The component of the output C 0 0 is crossed by no signal, so with B₀ or A₀ a matrix unit, the slices separate; the unit vector at A i j moves C i k when B₀ = E j k, and the unit vector at B j k moves C i k when A₀ = E i j. So the component holds every input and output.

The finite bounds (half_sq_le_of_matMul_of_totallyRegular, sq_sub_le_of_matMul, half_sq_le_of_matMul_polynomial). The terminals lie on distinct wires (terminal_injective_of_matMul). Along the ranking of MultiOutput.exists_rank, the threshold prefix (Tripartite.exists_threshold), the first prefix with at least ⌈3 n/2⌉ heavy vertices (with at least n placed terminals), ends at a terminal and has at most ⌈3 n/2⌉ + 1 of them. Charging each terminal with one heavy and one light endpoint to its light endpoint if placed and to its heavy endpoint otherwise gives 3 n² ≤ 2 (R_I + R_J + R_K) + 3 (Tripartite.three_mul_sq_le_two_mul_charge). Charged to the component holding all 2 n² inputs, a circuit of size s therefore has (n² - 1)/2 ≤ (A + η) (s - 2 n²)⁺ + 3 log₂ (2 n² + 3 s) + C with a totally regular matrix or for polynomial gates over any field, and (n² - 8 n - 1)/2 ≤ (A + η) (s - 2 n²)⁺ + 3 log₂ (2 n² + 3 s) + C over every finite field.

The asymptotic bounds (eventually_lt_size_of_matMul, eventually_lt_size_of_matMul_polynomial, eventually_lt_arithmeticCost_of_matMul). With the edge-score ordering coefficient A = 2 κ_E, where κ_E = Gaussian.frontierCoefficient ≈ 0.14035, for every ε > 0 and all large n, every such circuit has more than (2 + 1/(4 κ_E) - ε) n² gates, the coefficient being 2 + π/(6 arccos((1 + 2√2)/4)) ≈ 3.7812; as 2 κ_E ≤ 9/32, also more than (34/9 - ε) n² gates. The threshold depends only on ε, not on the field or the signature. The bound holds

for circuits with arbitrary fan-in-two gates over every finite field (eventually_lt_size_of_matMul), in particular over GF(2) = ZMod 2 (eventually_lt_size_matMul_zmod_two),
for formal computation with polynomial gates of fan-in at most two over every field (eventually_lt_size_of_matMul_polynomial),
for computation of the matrix product function with polynomial gates of fan-in at most two over every infinite field (eventually_lt_size_of_matMul_of_infinite), and
for the number of additions and multiplications of arithmetic circuits, with arbitrary constants free, computing the matrix product over every infinite field (eventually_lt_arithmeticCost_of_matMul) or formally over every field (eventually_lt_arithmeticCost_of_matMul_formal).

Prior art. Lower bounds for matrix multiplication usually count the multiplications of bilinear or quadratic algorithms in arithmetic models: Bläser (STACS 2001) proves 5/2 n² - 3 n multiplications, and Shpilka (SICOMP 2003) 3 n² - o(n²) product gates over GF(2) for bilinear and quadratic circuits. We know of no earlier bound beyond the trivial ≈ 2 n² on the number of gates of circuits with arbitrary fan-in-two gates, or over B₂, computing the matrix product.

Lower bounds for matrix multiplication #

Matrix multiplication in coordinates #

Circuits for matrix multiplication #

Asymptotic bounds #