哈佛、MIT学者联手，创下矩阵乘法运算最快纪录

矩阵乘法作为一种基本的数学运算，在计算机科学领域有着非常广泛的应用，矩阵乘法的快速算法对科学计算有着极为重要的意义。自 1969 年 Strassen 算法开始，人们意识到了快速算法的存在，开始了长达数十年的探索研究。

当你拥有两个大小一致的矩阵时，则可以将它们相乘得到第三个矩阵。例如，一对 2×2 矩阵的乘积也将是 2×2 矩阵，包含 4 个元素。即一对 n×n 矩阵的乘积是具有 n^2 个元素的另一个 n×n 矩阵。

因此，矩阵乘法至少需要 n^2 步，人们理想中的计算复杂度也就是 O(n^2)。

2020 年 10 月，来自哈佛大学与 MIT 的两位研究者发表了一篇论文，他们创建了有史以来矩阵相乘的最快算法，相比于之前最快算法，计算复杂度下降了 10 万分之一。其中，论文一作 Josh Alman 是哈佛大学的博士后研究生，主要研究算法设计与复杂度理论。二作 Vassilevska Williams 是 MIT 计算机科学与人工智能实验室（CSAIL）副教授，致力于将组合和图论工具应用于计算领域。

图（左）Josh Alman；图（右） Virginia Vassilevska Williams。

论文地址：https://arxiv.org/pdf/2010.05846.pdf

矩阵乘法的运算方法

为了了解该过程及其改进方法，我们首先来看一对 2 x 2 的矩阵，分别为矩阵 A 和矩阵 B。在计算它们的乘积时，需要使用矩阵 A 的对应行和矩阵 B 的对应列。具体运算方法如下图所示：

上述运算被称为矩阵的内积（inner product），按照上图所示的方法可以计算乘积矩阵中其他元素的值。对于上图的情况，这样的方法需要进行 8 次乘法运算，还有一些加法运算。通常，两个 n x n 矩阵相乘，一共需要 n^3 次乘法运算。

随着矩阵的增大，矩阵乘法所需的乘法运算数量比加法运算涨得快得多。通常，研究人员仅根据所需的乘法次数来度量矩阵乘法的运算速度。

几个世纪以来，人们一直认为 n^3 就是完成矩阵乘法最快的速度。Strassen 提出了一组复杂的关系，从而利用 14 次加法替换了上述 8 个乘法之一。

1981 年，Arnold Schönhage 利用这种方法证明了矩阵乘法的计算复杂度可以降低至 O(n^2.522)，Strassen 后来将此方法称为 laser 方法。

创造新纪录

几十年以来，矩阵乘法运算的每次提速都得益于 laser 方法的改进，原因是研究者们找到了在这两类问题之间进行转换的高效方法。Alman 和 Vassilevska Williams 的新方法也是如此。

矩阵乘法中，两个 n x n 矩阵的计算复杂度可以用

表示，其中

此前最快的纪录是 2014 年 François Le Gall 创造的，其中：

而在 Alman 和 Vassilevska Williams 的新方法中：

具体地讲，他们将复杂度降至了 O(n^2.3728596)，创造了矩阵乘法运算最快的新纪录。

值得一提的是，2012 年 Vassilevska Williams 就曾将这一数字降至 n^2.372873，不过在 2014 年被 François Le Gall 的 n^2.3728639 打破了。

然而，尽管这种方法为矩阵乘法的速度带来了一定的改进，但可以看到，改进的幅度越来越小。

日本名古屋大学数学研究生院副教授 François Le Gall。

实际上，Alman 和 Vassilevska Williams 的改进可能已经达到了 laser 方法的极限，但仍与终极理论目标相去甚远。

加州理工学院计算机科学教授 Chris Umans 表示：「使用该研究中的方法不太可能将复杂度降至 O(n^2)」。若想达到，还需找到新的方法。