首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

哈佛、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)」。若想达到,还需找到新的方法。

  • 发表于:
  • 原文链接http://news.51cto.com/art/202103/652304.htm
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券