MathLabs

未解决问题，应用与计算数学, 代数学，1969年提出

矩阵乘法指数 ω\omega

未解决

设 ω\omega 为使得域上两个 n×nn \times n 矩阵可用 O(nτ)O(n^\tau) 次算术运算相乘的所有实数 τ\tau 的下确界。确定 ω\omega 的精确值；特别地，是否有 ω=2\omega = 2？

研究前沿 截至2026年

截至2026年，ω\omega 的精确值仍在 22 与 2.3711772.371177 之间悬而未决。2023至2024年间，段然、吴洪勋、周任飞以及阿尔曼、段然、瓦西列夫斯卡·威廉姆斯、徐胤展、徐子轩、周任飞通过激光法中的非对称组合损耗分析将 ω\omega 降至 2.3713392.371339，而2026年迪蓬等人的预印本进一步求解了第 44 层优化问题，得到 ω<2.371177\omega < 2.371177。然而障碍性结果表明，仅靠科珀史密斯–维诺格拉德张量族本身无法达到 ω=2\omega = 2。

已知最佳结果

  • 基于非对称组合损耗的已发表激光法改进确立了 ω<2.371339\omega < 2.371339（阿尔曼、段然、瓦西列夫斯卡·威廉姆斯、徐胤展、徐子轩与周任飞，2024/2025年），而2026年迪蓬等人的预印本进一步认证了 ω<2.371177\omega < 2.371177。
  • 安拜尼斯、菲尔姆斯与勒加尔（2015年）证明，对科珀史密斯–维诺格拉德张量的幂应用激光法无法证明 ω<2.3078\omega < 2.3078。

使用的方法及其局限

方法取得的结果局限所在
施特拉森激光法与非对称组合损耗分析通过分析科珀史密斯–维诺格拉德张量的高次张量幂，将 ω\omega 的上界从 2.4792.479 逐步降至 2.3711772.371177受限于本质障碍（如科珀史密斯–维诺格拉德族的 ω≥2.3078\omega \ge 2.3078 下限）以及优化参数规模随递归层数呈双指数增长
边界秩与渐近和不等式将矩阵乘法张量直和的近似分解转化为 ω\omega 的有效渐近上界需要寻找低边界秩且高价值的初始张量，而目前尚无已知张量族能逼近 ω=2\omega = 2

尚未解决的问题

  • 是否成立 ω=2\omega = 2，即对任意 ε>0\varepsilon > 0，两个 n×nn \times n 矩阵都可以在 O(n2+ε)O(n^{2 + \varepsilon}) 次运算内完成相乘？
  • 对于计算 n×nn \times n 矩阵乘法的一般算术电路，能否证明任何严格优于 2n22n^2 量级的无条件下界？

参考文献

  1. Volker Strassen (1969). Gaussian elimination is not optimal · DOI:10.1007/BF02165411
  2. Don Coppersmith, Shmuel Winograd (1990). Matrix multiplication via arithmetic progressions · DOI:10.1016/S0747-7171(08)80013-2
  3. Ran Duan, Hongxun Wu, Renfei Zhou (2023). Faster Matrix Multiplication via Asymmetric Hashing · DOI:10.1109/FOCS57990.2023.00035 · arXiv:2210.10173
  4. Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou (2024). More Asymmetry Yields Faster Matrix Multiplication · arXiv:2404.16349