酷应用

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

百家 作者：机器之心 2021-03-24 15:52:51

选自quantamagazine

作者：Kevin Hartnett
机器之心编译
编辑：小舟、维度

作为一种基本数学运算，矩阵乘法的运算速度一直是一个重要的研究课题。哈佛大学和 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)」。若想达到，还需找到新的方法。

感兴趣的读者可以阅读论文原文，了解更多改进细节。

原文链接：https://www.quantamagazine.org/mathematicians-inch-closer-to-matrix-multiplication-goal-20210323/

中文NLP：2021海华AI挑战赛火热报名中！

由海华研究院与清华大学交叉信息研究院联合主办的“2021海华AI挑战赛·中文阅读理解”正在进行，上届决赛答辩仪式，姚期智院士为大家深情致辞，所有获奖选手也都收到了姚先生亲笔签名的证书。

本届大赛依然保留中学组及技术组两条赛道，共设30万元奖金池，诗词AI，智慧中文，点击阅读原文或立即扫码报名！

© THE END 

转载请联系本公众号获得授权

投稿或寻求报道：content@jiqizhixin.com

关注公众号：拾黑（shiheibook）了解更多

[广告]赞助链接：

四季很好，只要有你，文娱排行榜：https://www.yaopaiming.com/
让资讯触达的更精准有趣：https://www.0xu.cn/

*文章为作者独立观点，不代表 爱尖刀 立场
本文由 机器之心发表，转载此文章须经作者同意，并请附上出处( 爱尖刀 )及本页链接。
原文链接 https://www.ijiandao.com/2b/baijia/405786.html
哈佛
图库
机器之心 机器之心
公众号 关注网络尖刀微信公众号
随时掌握互联网精彩
赞助链接
百度热搜榜
排名 热点 搜索指数
iTrust
AiDeep Ued
关于我们 联系我们 升级日志 法律声明 广告服务 侵删通道
Copyright © 2021 K2CMS All rights reserved.
京ICP备14006288号