OpenAI 的 O(n^2.25) 快速矩阵乘法算法被推广至一般数域

aran_nayebi · x · 2026-10-08

有人将 OpenAI 团队的 O(n^{2.25}) 快速矩阵乘法（FMM）算法从复数域推广到了一般域，并在 Lean 中完成形式化验证。被引帖指出这篇新 FMM 论文出乎意料地优雅：不同于以往对 CW 张量做幂运算再裁剪的思路，它定义了张量上的势函数，通过研究简单的卷积张量以反证法完成整个证明。讨论者还认为 n^{9/4} 可能真就是矩阵乘法复杂度的正确指数；arapnayebi 补充称 SETH 或许是下一个被改进的方向，而 APSP 与 3SUM 此前的改进会带动其他归约问题的进步，且该矩阵乘法结果已被轻松推广。