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

编者按：本文来自微信公众号“机器之心”（ID:almosthuman2014），选自quantamagazine，作者：Kevin Hartnett，编译编辑：小舟、维度，36氪经授权发布。
作为一种基本数学运算，矩阵乘法的运算速度一直是一个重要的研究课题。哈佛大学和 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
矩阵乘法的运算方法【乘法|哈佛、MIT学者联手，创下矩阵乘法运算最快纪录】为了了解该过程及其改进方法，我们首先来看一对 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)，创造了矩阵乘法运算最快的新纪录。