2025-11-11T07:01:09.313379

Barriers for rectangular matrix multiplication

Christandl, Gall, Lysikov et al.

We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give algorithms with complexity $n^{p + 1}$ for $n \times n$ by $n \times n^p$ matrix multiplication. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously known barriers, both in the numerical sense, as well as in its generality. In particular, we prove that any lower bound on the dual exponent of matrix multiplication $Î±$ via the big Coppersmith-Winograd tensors cannot exceed 0.6218.

academic

Barriers for rectangular matrix multiplication

基本信息

论文ID: 2003.03019
标题: Barriers for rectangular matrix multiplication
作者: Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam
分类: cs.CC (Computational Complexity), math.AC (Commutative Algebra)
发表时间: November 10, 2025 (arXiv版本)
论文链接: https://arxiv.org/abs/2003.03019

摘要

本文研究了大型矩形矩阵乘法的算法问题。作者证明了用于构造最快矩形矩阵乘法算法的方法无法为 $n \times n$ 乘以 $n \times n^p$ 的矩阵乘法提供复杂度为 $n^{p+1}$ 的算法。实际上，作者为这种方法证明了精确的数值障碍。这一障碍在数值意义和通用性方面都改进了之前已知的障碍。特别地，作者证明了通过大Coppersmith-Winograd张量获得的矩阵乘法对偶指数 $\alpha$ 的任何下界都不能超过0.6218。

研究背景与动机

问题背景

矩阵乘法复杂性问题：给定两个大矩阵，需要多少标量算术运算来计算它们的矩阵乘积？标准算法对于两个 $n \times n$ 方阵需要约 $2n^3$ 次运算，但理论下界仅为 $n^2$ 。
矩形矩阵乘法：在实际应用中，待乘矩阵通常是矩形而非方阵。对于任意非负实数 $p$ ，给定 $n \times \lceil n^p \rceil$ 矩阵和 $\lceil n^p \rceil \times n$ 矩阵，需要多少运算来计算其乘积？
指数定义： $\omega(p)$ 表示任何算术算法所需运算次数中 $n$ 的最优指数，先验边界为 $\max(2, 1+p) \leq \omega(p) \leq 2+p$ 。

研究动机

理论重要性：理解 $\omega(p)$ 不仅对矩形矩阵乘法有意义，也是证明 $\omega = 2$ （方阵乘法的最优指数）的手段。
实际应用：矩形矩阵乘法在线性规划求解、经验风险最小化等领域有直接应用。
技术局限：当前技术在改进上界方面遇到瓶颈，需要理解其根本限制。

核心贡献

建立了通用障碍框架：为当前构造矩形矩阵乘法算法的主要技术建立了精确的数值障碍。
改进了数值界限：在数值意义和通用性方面都改进了之前的障碍结果。
引入虚拟矩阵乘法张量：为处理非整数 $p$ 的情况，引入了新的数学工具。
分析催化性方法：研究了包含催化张量的更复杂算法结构。
对偶指数的精确界限：证明了通过Coppersmith-Winograd张量获得的 $\alpha$ 下界不能超过0.6218。

方法详解

任务定义

研究矩形矩阵乘法问题：给定 $n \times \lceil n^p \rceil$ 矩阵 $A$ 和 $\lceil n^p \rceil \times n$ 矩阵 $B$ ，计算乘积 $AB$ 所需的算术运算次数。目标是理解当前技术在改进复杂度上界 $\omega(p)$ 方面的根本限制。

核心理论框架

1. 张量表示

矩阵乘法问题对应于张量族：

$\ell \times m$ 矩阵乘以 $m \times n$ 矩阵对应张量： $\langle \ell, m, n \rangle = \sum_{i=1}^\ell \sum_{j=1}^m \sum_{k=1}^n x_{ij}y_{jk}z_{ki}$
单位问题对应对角张量： $\langle n \rangle = \sum_{i=1}^n x_i y_i z_i$

2. 约化概念

定义了多种张量约化类型：

限制 ( $S \leq T$ )：存在线性映射使得 $S = T \circ (A,B,C)$
退化 ( $S \triangleleft T$ )： $S = \lim_{\epsilon \to 0} T(A(\epsilon)x, B(\epsilon)y, C(\epsilon)z)$
单项式限制/退化：矩阵 $A,B,C$ 每行每列最多一个非零元素

3. 适当张量参数

定义了适当张量参数类 $F$ ，需满足：

$\leq$ -单调性： $S \leq T \Rightarrow F(S) \leq F(T)$
$\otimes$ -次乘性： $F(S \otimes T) \leq F(S) \cdot F(T)$
MaMu- $\otimes$ -乘性： $F(\langle \ell_1\ell_2, m_1m_2, n_1n_2 \rangle) = F(\langle \ell_1,m_1,n_1 \rangle) \cdot F(\langle \ell_2,m_2,n_2 \rangle)$
自 $\oplus$ -加性： $F(T^{\oplus s}) = s \cdot F(T)$
渐近秩界限： $F(T) \leq \tilde{R}(T)$

技术创新点

1. 虚拟矩阵乘法张量

为处理实数 $p$ ，引入形式符号 $\langle 2,2,2^p \rangle$ ：

当 $p = \log_a b$ （ $a,b$ 为正整数）时： $F(\langle 2,2,2^p \rangle) = 2^{\log_a F(\langle a,a,b \rangle)}$
否则通过下确界定义： $F(\langle 2,2,2^p \rangle) = \inf\{F(\langle 2,2,2^P \rangle) | P \geq p, \exists a,b \in \mathbb{Z}_{\geq 0}: P = \log_a b\}$