4×4 复矩阵乘法：AlphaEvolve 找到 48 次乘法的算法

AlphaEvolve 找到只需 48 次标量乘法的 4×4 复矩阵乘法算法，改进了递归使用 Strassen 方法所需的 49 次。

问题
两个 4×44 \times 4 复矩阵相乘最少需要多少次标量乘法
贡献方
AlphaEvolve（Google DeepMind） · 大语言模型驱动的进化式代码搜索
验证
可直接验算
时间线
Strassen 1969 → AI 改进 2025-05
来源
DeepMind 博客
部分
结果改进上界

问题

1969 年，Strassen 发现两个 2×22 \times 2 矩阵相乘只需要 7 次标量乘法，而不是朴素的 8 次。把这个方法递归用在 4×44 \times 4 矩阵上，需要 72=497^2 = 49 次乘法。此后半个多世纪，对于复数矩阵没有人找到更少的做法。

AI 做了什么

AlphaEvolve 让大语言模型不断提出并改写搜索算法的代码，由自动评估器检验正确性和乘法次数。它找到了一个只需 48 次标量乘法的 4×44 \times 4 复矩阵乘法算法。

如何验证

算法是一组明确的线性组合与乘积，代入符号矩阵即可逐项检验结果是否等于矩阵乘积。

局限

这改进的是上界：48 是否最少仍然未知。结果针对复数域，并且常数级的改进对实际计算速度的影响有限。

∎