MathLabs

未解決問題、応用数学と計算数学, 代数学、1969年に提起

行列乗算の指数 ω\omega

未解決

体上の2つの n×nn \times n 行列を O(nτ)O(n^\tau) 回の算術演算で乗算できるような実数 τ\tau の下限を ω\omega とする。ω\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 に対して2つの 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