通过打消「公开的低效」课题，盘算机科学家提出了一种比以往更快的大型矩阵相乘新方式。
矩阵乘法作为众多 GPU 算子的基础操作，是高性能盘算的重要课题之一，也是 AI 等应用的基石。它的算法机制本身相当简单，但为了达到更快的速度，人们多年来不懈努力，优化程度却一直有限。
今日，在《量子杂志》的一篇报道中，我们看到了推动矩阵乘法速度进一步提升的两篇论文，其中清华姚班一位大四本科生全程参与了两篇论文的撰写，为该领域的算法改善带来了全新的希望。
矩阵乘法改善出现新「奇点」
盘算机科学家是一群要求很高的人。对于他们来说，仅仅获得课题的正确答案是不够的，往往还要尽可能高效地获得答案。
我们以矩阵或数字数组相乘为例，1812 年，法国数学家 Jacques Philippe Marie Binet 提出了一套人们至今仍在教授学生的基本规则。这套规则运行得很好，但已经有数学家找到了简化和加速该流程的方式。
法国数学家 Jacques Philippe Marie Binet。
现在，加速矩阵乘法流程的任务成为数学和盘算机科学的交叉点。研讨人员至今仍在继续改善该流程，尽管近几十年来进展相当有限。名古屋大学盘算机科学家 François Le Gall 表示，自 1987 年以来，矩阵乘法的数值改善「一直很小，而且极其难以实现」。
最近，来自清华大学的段然（Ran Duan）、周任飞（Renfei Zhou）和加州大学伯克利分校的 Hongxun Wu 在解决这个长期存在的课题上迈出了重要一步，撰写的论文足足有 87 页。对于三位研讨者的成果， Le Gall 表示尽管改善本身相对较小，但是「从概念上讲比以往的改善都大。」
该论文被盘算机科学领域的顶会 FOCS 2023 接收。
论文 v1 发布在 2022 年 10 月，v5 在 2023 年 11 月。论文地址：https://arxiv.org/abs/2210.10173
其中，段然为清华大学交叉信息研讨院副教授，主要研讨方向为图论算法、数据结构、盘算理论。Hongxun Wu 为加州大学伯克利分校二年级博士生，也是清华姚班出身。
周任飞为清华姚班 2020 级的大四本科生，主修理论盘算机科学（TCS）。他主要研讨（简洁）数据结构和快速矩阵乘法，并对 TCS 的其他领域具有广泛兴趣，比如流算法、博弈论和在线算法等。
此前，周任飞曾在理论盘算机科学顶级会议 FOCS/SODA 上发表多篇论文。
三位研讨者的论文揭示了以前未知且未开发的潜在改善来源，并且已经取得了成果。2024 年 1 月发表的第二篇论文（周任飞同样参与撰写）以此为基础，展示了如何进一步增强矩阵乘法。
论文地址：https://epubs.siam.org/doi/10.1137/1.9781611977912.134
哈佛大学理论盘算机科学家 William Kuszmaul 对此表示，这是一项重大的技术突破，是十多年来我们所看到的矩阵乘法的最大改善。
矩阵乘法要改善什么课题
矩阵乘法可能看起来是一个晦涩的课题，但它是一种基本的盘算操作。它被融入了人们每天使用的大部分算法中，用于各种任务，从显示更清晰的盘算机图形到解决网络理论中的物流课题。就像在盘算的其他领域一样，速度至关重要。即使是微小的改善终究也可能大大减少所需要的时间、盘算能力和金钱。但目前，理论家主要感兴趣的是弄清这个流程到底能够有多快。
传统的两个 n×n 矩阵相乘的方式 —— 即将第一个矩阵中每一行的数字与第二个矩阵中每一列的数字相乘 —— 需要进行 n³ 次独立的乘法操作。对于 2 乘 2 的矩阵而言，这意味着需要进行 2³，也就是 8 次乘法操作。
1969 年，数学家 Volker Strassen 发现了一种更精巧的方式，只需 7 个乘法方式和 18 个加法方式，就能完成 2×2 矩阵的乘法运算。两年后，盘算机科学家 Shmuel Winograd 证明，对于 2×2 矩阵来说，7 步乘法确实是绝对最小值。
Strassen 利用同样的想法证明，所有较大的 n×n 矩阵也可以用少于 n3 步的方式进行乘法运算。这一策略中的一个关键因素涉及一个称为分解的程序：将一个大矩阵分解成一个个更小的子矩阵，这些子矩阵终究可能小到 2×2 甚至 1×1（只是单个数字）。
对于将巨型数组分解成小块的理由相当简单，麻省理工学院的盘算机科学家 Virginia Vassilevska Williams 说：「对于一个大矩阵（比如 100×100 的矩阵），人类很难想到最佳的算法。」即使是 3 乘 3 的矩阵也还没有完全解决。「然而，人们可以使用已经为小矩阵开发的快速算法来获得更大矩阵的快速算法。」
研讨人员确定，速度的关键在于减少乘法方式的数量，尽可能将指数从 n3（传统方式）降低。可能的最低值 n² 基本上就是写出答案所需的时间。盘算机科学家把这个指数称为 Ω，即 ω。nω 是当 n 越来越大时，成功将两个 n×n 矩阵相乘所需的最少方式。同为 2024 年 1 月论文合著者的周任飞说：「这项工作的重点，是看你能接近 2 多少，并且是否可以在理论上实现。」
激光法
1986 年，Strassen 取得了另一项重大突破，他推出了矩阵乘法的激光法。Strassen 用它确定了 ω 的上限值为 2.48。虽然该方式只是大型矩阵乘法的一个方式，但却是最重要的方式之一，因为研讨人员一直在不断改善它。
一年后，Winograd 和 Don Coppersmith 推出了一种新算法，对激光法进行了完美的补充。这套工具的组合在后来几乎所有加速矩阵乘法的研讨中都得到了应用。
下面是一个简化的方式，让我们来看看这些不同的元素是如何结合在一起的。让我们从两个大型矩阵 A 和 B 开始，将它们相乘。首先，你要把它们分解成许多较小的子矩阵，有时也叫块。接下来，你就可以使用 Coppersmith 和 Winograd 的算法，将其作为处理并终究组装这些块的指导手册。Vassilevska Williams 说：「它告诉我在乘积矩阵 C 中要乘什么、加什么，以及哪些元素在哪里。」「它只是一个从 A 和 B 建立 C 的『配方』」。
然而，这里有一个课题：有时你会得到具有共同元素的块。保留这些共同元素会相当于将这些元素盘算两次，因此在某个时候，需要打消这些堆叠部分。研讨人员通过「消灭」它们所在的块来解决这个课题 —— 将它们的分量设置为零以将它们从盘算中移除。
Virginia Vassilevska Williams 是改善矩阵乘法新方式的团队成员之一，她提出了目前最快的方式。
这就是 Strassen 的激光法终究发挥作用的地方。Le Gall 说，「激光法通常非常有效，并且通常能找到打消堆叠的子块的好方式」。在激光打消了所有堆叠之后，你就可以构建终究的乘积矩阵 C。
将这些各种技术结合起来，就得到了一种用尽量少的乘法总数来乘两个矩阵的算法，至少在理论上是这样。激光法并不是为了实际应用；它只是一种思考矩阵相乘的理想方式。周任飞表示，「我们从未在盘算机上运行这种方式，我们进行对它的分析。」
正是这种分析促成了 ω 十多年来的最大改善。
被发现的「公开损失」
在段然、周任飞和 Hongxun Wu 的第一篇论文《Faster Matrix Multiplication via Asymmetric Hashing》中，他们表明，施特拉森算法的进程可以大大加快。这一切要得益于他们称之为「公开损失」（hidden loss）的概念。周任飞表示，该概念深深地公开在以前的分析中，是无意中打消了太多块的结果。
激光法的工作原理是将堆叠的块标记为垃圾，并安排处理，而其他块被认为有价值并将被保存。不过，选择流程有些随机。事实上，被标记为垃圾的块可能终究还是有用的。
这并不完全令人惊讶，但通过检查许多随机选择，段然团队确定激光法系统性地低估了块的价值，因此应该保存更多的块，减少扔掉的块。而且，正如通常的情况一样，更少的浪费可以转化为更高的效率。
对于段然团队的做法，Le Gall 认为，「能够保留更多块而不堆叠，这种做法实现了更快的矩阵乘法算法。」
在证明了这种损失的存在后，段然团队修改了激光法标记块的方式，从而大大减少了浪费。他们将 ω 的新上限设定在了 2.371866 左右，这要比 Josh Alman 和 Vassilevska Williams 在 2020 年设定的上限 2.3728596 有所改善。
这看起来是一个不大的变化，将上限降低了大约 0.001，但这是自 2010 年以来科学家们看到的最大进步。相比之下，Vassilevska Williams 和 Alman 2020 年的结果只比之前的结果提高了 0.00001。
当然，对研讨人员来说，最令人兴奋的不仅仅是新纪录本身，该记录并没有持续多久。事实上，这篇论文揭示了一种新的改善途径，而在此之前，这种途径完全没有被注意到。
Le Gall 称，近四十年来，每个人都依赖相同的激光法。随着段然等三位研讨者的论文出现，我们可以做得更好。
因此，周任飞参与撰写的 2024 年 1 月的论文改善了这种新方式，进一步减少了公开损失。他们又进一步提高了 ω 的上限，使它降低到了 2.371552。
研讨者还使用同样的方式来改善矩形（n×m）矩阵的乘法流程，该乘法流程在图论、机器学习和其他领域均有广泛应用。
沿着这些方向取得一些进一步的进展几乎是肯定的，但这是有限度的。2015 年，Le Gall 和两位合作者证明，目前的方式，也就是激光法，再加上 Coppersmith 和 Winograd 的方式，无法得到低于 2.3078 的 ω。
Le Gall 说：「要想进一步改善，就必须在 Coppersmith and Winograd 的原始方式基础上加以改善，而这种方式自 1987 年以来就没有真正改变过。」但到目前为止，还没有人提出更好的方式。也许根本就没有。
周任飞说：「改善 ω 实际上是理解这个课题的一部分。如果我们能很好地理解这个课题，就能设计出更好的算法。不过，人们对这个古老课题的理解还处于非常初级的阶段。」
原文链接：
https://www.quantamagazine.org/new-breakthrough-brings-matrix-multiplication-closer-to-ideal-20240307/