在长期存在的理论计算谜题中追求完美

40 年来，一个未被注意到的疏忽掌握了解决计算机科学中长期悬而未决问题的关键。

这些进步可以帮助推动技术进步，例如训练人工智能。

图片来源：agsandrew/Shutterstock.com

对于 21 世纪的大多数人来说，学习乘法表的记忆已经成为一个笑话。我们被警告说：“作为一个成年人，你的口袋里不会每天都有计算器。”好吧，这就是你所知道的，希金博顿夫人；如今，我们几乎 100% 的人口袋里不仅有计算器，还可以访问迄今为止收集的全部人类知识。

然而，数学家和计算机科学家并不是大多数人。至少从 19 世纪初期开始，城里就出现了一种新型乘法：矩阵乘法——即使在今天，凭借我们所有的技术实力，这仍然是一个真正的问题。

但这是必须的吗？两项新结果——一项是 2023 年 11 月的结果，另一项是 1 月份发布的——暗示答案是否定的——或者至少“没有我们之前想象的那么严重”。 ” 

矩阵乘法的问题

那么，第一个问题：矩阵到底是什么？不幸的是，答案远不如电影改编的那么酷。

简而言之，矩阵只是数字的矩形数组——或者其他数学对象，如符号或表达式，甚至其他矩阵，因为有时我们都觉得有点受虐——按行和列排列。它们在数学和科学中具有非常广泛的用途，因此能够操纵它们......嗯，非常重要。

现在，将两个矩阵相乘，你会得到另一个矩阵——只要满足一些规定。首先，只有当左侧矩阵的列数与右侧矩阵的行数相同时，才能将两个矩阵相乘，如下所示：

正确处理这一点很重要，因为与普通乘法不同，矩阵运算不可交换 - 也就是说，顺序很重要。给定两个矩阵 A 和 B，您完全有可能能够算出矩阵乘积 AB ，但不能算出 BA ;即使两者都有可能，也没有特别的理由让他们给出相同的答案。

那么，一旦我们满足了所有这些要求，我们如何真正找到两个矩阵的乘积呢？用数学符号表示，答案如下所示：

我们承认，这实际上可能没有太大帮助。让我们看一个例子。

现在你可能已经明白矩阵乘法比常规乘法涉及更多的工作 - 你是完全正确的。这就是为什么拥有一个可以为我们完成这一切的计算机程序将是一个福音——但事实证明，即使这也是一个问题。

进展缓慢

“自从计算机时代到来以来，研究人员一直在努力寻找矩阵相乘的最佳方法，这是一种基本运算，也是许多重要算法的瓶颈，”Sara Robinson 在 2005 年关于该问题的一篇文章中为 SIAM News 解释道。 。 

“更快的矩阵乘法将为许多标准线性代数问题提供更有效的算法，例如矩阵求逆、求解线性方程组以及查找行列式，”文章继续说道。 “即使是一些基本的图算法的运行速度也只能与矩阵乘法一样快。 ”

所以问题就变成了：到底有多快？遗憾的是，答案是“从历史上看，根本没有那么快。” ” 给定几个矩阵，假设每个矩阵有 100 行和 100 列，您需要执行 1,000,000 次乘法才能找到它们的乘积 - 而且这个数字呈三次方增长，而不是线性增长。换句话说：只需将这些矩阵增加一行和一列，解决问题所需的乘法次数就会增加 30,000 多次。

现在，这并不是说我们不能做得更快——事实上，多年来已经进行了大量研究来寻找实现这一目标的方法。该领域的大多数专家认为我们最终会在二次时间达到顶峰：应该可以使用 10,000 步（但不能更少）来乘以一对 100×100 矩阵。但究竟如何实现这一目标仍然是计算机科学中的一个重大开放问题。

清华大学理论计算机科学系学生、新论文合著者周仁飞今年早些时候告诉《广达》杂志：“这项工作的目的是看看你能有多接近两个，以及是否可以理论上可以实现。 ”

我们已经取得了一些进展。自 1969 年数学家 Volker Strassen 首次研究更高效的矩阵乘法算法以来，时间指数已从 3 降至 2.4 以下 - 或者换句话说，只需不到 64,000 次计算即可将这 100 倍相乘-100 个矩阵在一起。但这是一个艰难的过程——自 80 年代末以来，改进一直“很小，而且 […] 极其难以实现”，名古屋大学计算机科学家弗朗索瓦·勒加尔 (François Le Gall) 告诉广达。

那么，您可能会想，为什么我们应该对一些新的改进感到兴奋呢？毕竟，从纯粹的数字角度来看，收益并没有那么显着。

然而，勒加尔告诉广达，这一突破“在概念上比之前的其他突破更大”。那么是什么让它如此特别呢？

不断改进

要了解 11 月至 1 月期间清除的障碍，我们应该事先了解一下情况 - 事实证明，这有点像大杂烩。

1986年和1987年，出现了两项重大突破：首先，Volker Strassen——是的，又是他——提出了现在被称为矩阵乘法的激光方法；一年后，计算机科学家 Shmuel Winograd 和密码学家 Don Coppersmith 开发了一种算法，专门用于补充和改进 Strassen 的工作。

将这两种技术结合起来的结果是相当巧妙的。 Strassen 早在 60 年代的最初贡献就是注意到，通过用分块矩阵重写矩阵 A 和 B，也就是说，将它们视为其元素为是其他矩阵 - 只要您执行以下操作，就可以在少于 n3 次计算中找到它们的乘积 A∙B=C正确的计算。

那么，弄清楚你需要做什么，就是 Coppersmith 和 Winograd 的用武之地。麻省理工学院的计算机科学家 Virginia Vassilevska Williams 表示，他们的算法“告诉我什么要相乘，什么要相加，什么条目去哪里”其中一篇新论文的合著者告诉广达。 “这只是从A和B构建C的秘诀。 ”

这就是激光方法发挥作用的地方。虽然 Coppersmith 和 Winograd 的算法非常出色，但它并不完美。它通常会导致一些冗余，各种术语到处“重叠”。激光是计算机科学家旨在“剪掉”这些重复项的方式：它“通常效果很好，”勒加尔说，“并且通常会找到一种好方法来杀死一部分块以消除重叠。 ”

但就像 2000 年代初期的美容师面对一双自然眉毛一样，有时您可能会用激光去除太多眉毛。 Le Gall 告诉 Quanta：“能够保留更多的块而不重叠，从而导致 [...] 更快的矩阵乘法算法。”而这正是 Duan 团队的技术所依赖的认识。

重新平衡天平

通过修改激光方法为矩阵中的块分配权重的方式（它认为它们有多重要，因此它们被保留而不是被删除的可能性有多大），团队成功地将矩阵乘法的计算时间减少了最多十多年来数额巨大。 

现在，不要太兴奋——他们只是把它从 2.373 降到了 2.372。但这并不是真正的重点：让计算机科学家兴奋的不是所取得的结果，而是团队是如何做到的。经过近四十年对同一算法组合进行无限小的改进后，勒加尔告诉广达，“他们发现，我们可以做得更好。 ”

到底有多好还有待观察——但如果您想知道这些突破性的结果可以应用于哪些实际应用，您可能会发现自己有点失望。激光方法本身已经是所谓的“银河算法”——如此命名是因为它从未用于解决地球上的任何问题——并且除非量子计算的状态发生一些不可预见的巨大变化，同样的情况也将不可避免地适用于新改进的算法。版本。 

“我们从不运行这个方法，”周证实。 “我们对其进行分析。 ”