用神经网络复现斯特拉森算法，发现3×3矩阵乘法最低有效秩为23
Neural Learning of Fast Matrix Multiplication Algorithms: A StrassenNet Approach
- 构建StrassenNet神经架构，通过学习张量低秩分解实现快速矩阵乘法
- 2×2乘法始终收敛到7秩解，验证了斯特拉森算法最优性；3×3乘法在23秩时误差显著下降
- 首次用神经方法揭示3×3矩阵乘法的潜在最小有效秩，适合理论计算与算法设计研究者
快速矩阵乘法可表述为对矩阵乘法张量进行低秩分解。我们设计了一种神经架构StrassenNet，成功复现了2×2矩阵乘法的斯特拉森算法。在多次独立训练中，网络始终收敛至7秩张量，数值上重现了斯特拉森的最优解。随后，我们在3×3矩阵乘法上训练相同架构，秩r∈{19,…,23}。实验揭示明确的数值阈值：秩为23的模型验证误差显著低于秩≤22的模型，表明23可能是3×3矩阵乘法张量的实际最小有效秩。我们还通过ε-参数化拓展方法至边界秩分解，初步结果与已知的3×3矩阵乘法边界秩上界一致。
原文摘要 · Abstract (English)
Fast matrix multiplication can be described as searching for low-rank decompositions of the matrix--multiplication tensor. We design a neural architecture, \textsc{StrassenNet}, which reproduces the Strassen algorithm for $2\times 2$ multiplication. Across many independent runs the network always converges to a rank-$7$ tensor, thus numerically recovering Strassen's optimal algorithm. We then train the same architecture on $3\times 3$ multiplication with rank $r\in\{19,\dots,23\}$. Our experiments reveal a clear numerical threshold: models with $r=23$ attain significantly lower validation error than those with $r\le 22$, suggesting that $r=23$ could actually be the smallest effective rank of the matrix multiplication tensor $3\times 3$. We also sketch an extension of the method to border-rank decompositions via an $\varepsilon$--parametrisation and report preliminary results consistent with the known bounds for the border rank of the $3\times 3$ matrix--multiplication tensor.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。