新突破使矩阵乘法更接近理想 |广达杂志

计算机科学家是一群要求很高的人。对于他们来说，仅仅获得问题的正确答案是不够的——目标几乎总是尽可能高效地获得答案。

以矩阵或数字数组相乘为例。 1812 年，法国数学家雅克·菲利普·玛丽·比奈 (Jacques Philippe Marie Binet) 提出了我们至今仍在教给学生的一套基本规则。它运行得非常好，但其他数学家已经找到了简化和加速该过程的方法。现在的任务是 加快进程 矩阵乘法的原理是数学和计算机科学的交叉点，研究人员至今仍在继续改进这一过程——尽管近几十年来进展相当有限。自 1987 年以来，矩阵乘法的数值改进一直“很小而且……极其难以实现”， 弗朗索瓦·勒加尔名古屋大学计算机科学家。

现在，三位研究人员——清华大学的段燃和周仁飞以及加州大学伯克利分校的吴洪勋——在解决这个长期存在的问题上迈出了重要的一步。他们的 新的结果Le Gall 表示，去年 11 月在计算机科学基础会议上提出的这项技术源于一项意想不到的新技术。尽管改进本身相对较小，但勒加尔称其“在概念上比之前的其他改进更大”。

该技术揭示了以前未知且尚未开发的潜在改进来源，并且已经取得了成果： 第二篇论文于一月份发表，以第一个版本为基础，展示了如何进一步增强矩阵乘法。

“这是一项重大技术突破，” 威廉·库兹莫尔，哈佛大学理论计算机科学家。 “这是十多年来我们所看到的矩阵乘法的最大改进。”

输入矩阵

这似乎是一个晦涩的问题，但矩阵乘法是基本的计算运算。它被纳入人们每天用于各种任务的大部分算法中，从显示更清晰的计算机图形到解决网络理论中的逻辑问题。与其他计算领域一样，速度至关重要。即使是微小的改进最终也可能会显着节省时间、计算能力和金钱。但目前，理论家主要感兴趣的是弄清楚这个过程到底有多快。

传统的二乘法 n逐n 矩阵 - 将第一个矩阵中每一行的数字乘以第二个矩阵中列中的数字 - 需要 n³ 单独的乘法。对于 2×2 矩阵，这意味着 2³ 或 8 次乘法。

1969 年，数学家 Volker Strassen 揭示了一个更复杂的过程，只需 2 个乘法步骤和 2 个加法即可完成 18×2 矩阵的乘法。两年后，计算机科学家 Shmuel Winograd 证明，2 确实是 XNUMX×XNUMX 矩阵的绝对最小值。

施特拉森利用同样的想法来证明所有更大的 n逐n 矩阵相乘也可以少于 n³ 脚步。该策略的一个关键要素涉及一个称为分解的过程 - 将大矩阵分解为连续较小的子矩阵，这些子矩阵最终可能小至 2×2 甚至 1×1（这些只是单个数字）。

根据说法，将巨大数组分成小块的基本原理非常简单 弗吉尼亚·瓦西列夫斯卡·威廉姆斯（Virginia Vassilevska Williams）麻省理工学院的计算机科学家，也是其中一篇新论文的合著者。 “人类很难看着一个大矩阵（例如，100×100 的量级）并想到最好的算法，”Vassilevska Williams 说。即使是 3×3 矩阵也还没有完全解决。 “尽管如此，人们可以使用一种已经为小矩阵开发的快速算法来获得针对较大矩阵的快速算法。”

研究人员确定，速度的关键是减少乘法步骤的数量，从而降低指数 n³ （对于标准方法）尽可能多。尽可能低的值， n²，基本上只要写出答案就可以了。计算机科学家将该指数称为 omega、ω，其中 n^ω 成功地将两个相乘所需的最少步骤 n逐n 矩阵为 n 长得很大。 “这项工作的目的，”周说，他也是 2024 年 2 月论文的合著者，“是看看你能有多接近 XNUMX，以及理论上是否可以实现。”

激光聚焦

1986年，施特拉森又取得了重大突破，他 介绍 所谓的矩阵乘法激光法。 Strassen 使用它确定了 omega 的上限值 2.48。虽然该方法只是大型矩阵乘法的第一步，但它是最重要的步骤之一，因为研究人员不断对其进行改进。

一年后，维诺格拉德和唐·科珀史密斯推出了一种新算法，完美地补充了激光方法。这种工具组合几乎出现在随后所有加速矩阵乘法的努力中。

以下是思考这些不同元素如何组合在一起的简化方法。让我们从两个要相乘的大矩阵 A 和 B 开始。首先，将它们分解为许多较小的子矩阵或块（有时也称为块）。接下来，您可以使用 Coppersmith 和 Winograd 的算法作为处理和最终组装块的指导手册。 Vassilevska Williams 说：“它告诉我在乘积矩阵 C 中要相乘什么、要相加什么以及哪些条目去哪里”。 “这只是从 A 和 B 构建 C 的秘诀。”

然而，有一个问题：有时您最终会得到具有共同条目的块。将这些留在产品中类似于将这些条目计数两次，因此在某些时候您需要删除那些重复的术语（称为重叠）。研究人员通过“杀死”它们所在的块来做到这一点——将它们的分量设置为零以将它们从计算中删除。

这就是施特拉森的激光方法最终发挥作用的地方。 “激光方法通常效果很好，通常会找到一种很好的方法来杀死一部分块以消除重叠，”勒加尔说。在激光消除或“烧掉”所有重叠部分后，您可以构建最终的产品矩阵 C。

将这些不同的技术组合在一起会产生一种算法，用于将两个矩阵相乘，总体上故意减少乘法次数——至少在理论上是这样。激光方法并不实用；这只是思考矩阵乘法的理想方法的一种方法。 “我们从未[在计算机上]运行该方法，”周说。 “我们分析一下。”

这一分析为欧米茄带来了十多年来最大的改进。

发现损失

去年夏天段、周和吴发表的论文表明，施特拉森的进程仍然可以显着加快。这一切都是因为他们称之为隐藏损失的概念，该概念深深地埋藏在之前的分析中——“无意中杀死了太多区块的结果，”周说。

激光方法的工作原理是将重叠的块标记为垃圾，安排处理；其他块被认为是有价值的并且将被保存。然而，选择过程有些随机。事实上，被评为垃圾的区块可能最终还是有用的。这并不完全令人惊讶，但通过检查许多随机选择，段的团队确定激光方法系统性地低估了区块的价值：应该保存更多的区块，减少扔掉的区块。而且，正如通常的情况一样，更少的浪费可以转化为更高的效率。

“能够保留更多块而不重叠，从而导致……更快的矩阵乘法算法，”Le Gall 说。

在证明了这种损失的存在后，段的团队修改了激光方法标记块的方式，大大减少了浪费。因此，他们将 omega 的新上限设置为 2.371866​​2.3728596 左右 — 比之前的上限 XNUMX 有所改进， 设定于2020年 作者：乔什·阿尔曼和瓦西莱夫斯卡·威廉姆斯。这似乎是一个不大的变化，将界限降低了大约 0.001。但这是自 2010 年以来科学家们看到的最大的进步。相比之下，Vassilevska Williams 和 Alman 2020 年的结果只比之前的结果提高了 0.00001。

但对研究人员来说，最令人兴奋的不仅仅是新纪录本身——它并没有持续多久。事实上，这篇论文揭示了一种新的改进途径，而在此之前，这种途径完全没有被注意到。勒加尔说，近四十年来，每个人都依赖相同的激光方法。 “然后他们发现，好吧，我们可以做得更好。”

2024 年 2.371552 月的论文完善了这种新方法，使 Vassilevska Williams、Zhou 及其合著者能够进一步减少隐藏损失。这导致 omega 的上限进一步提高，将其降低至 XNUMX。作者还推广了相同的技术来改进矩形的乘法过程（n逐m) 矩阵——一种在图论、机器学习和其他领域有应用的过程。

沿着这些方向取得一些进一步的进展几乎是肯定的，但也存在局限性。 2015年，勒加尔和两位合作者 证明 当前的方法（激光方法与 Coppersmith-Winograd 配方相结合）无法产生低于 2.3078 的 omega。 Le Gall 说，要进行进一步的改进，“您需要改进 Coppersmith 和 Winograd 的原始[方法]，该方法自 1987 年以来就没有真正改变过设立的区域办事处外，我们在美国也开设了办事处，以便我们为当地客户提供更多的支持。“ 但到目前为止，还没有人想出更好的方法。甚至可能连一个都没有。

“改善欧米茄实际上是理解这个问题的一部分，”周说。 “如果我们能够很好地理解这个问题，那么我们就可以为其设计更好的算法。 [并且]人们对这个古老问题的理解仍处于早期阶段。”