华人学者彭泱获顶会最佳论文奖：如何最快求解“诺亚方舟上的鸡兔同笼问题”？靠“猜”

作者 | 陈彩娴、青暮

在大多数同学的记忆里，数学老师也许都说过这么一句话：“问题的答案不能靠猜！”

但是，近日，来自佐治亚理工学院的华人学者彭泱（Richard Peng）却凭借“迭代猜测”策略，提出了一种能够更快求解线性方程组的方法，并因此获得 2021 年算法顶会 ACM-SIAM 的最佳论文奖！

线性方程组是数学领域的奠基计算命题之一。去年 7 月，彭泱及其合作伙伴 Santosh Vempala 将一种求解线性方程组的新方法发表于 arXiv 上，今年 1 月在 ACM-SIAM 离散算法专题研讨会（ACM-SIAM Symposium on Discrete Algorithms，简称“SODA”）上展示，获得同行的一致肯定。

自1990年来，SODA每年举办一次，举办时间通常在一月份。该会议由ACM算法和计算理论特别兴趣小组（SIGACT）和SIAM离散数学活动小组共同赞助，其形式更像是理论计算机科学会议，而不是数学会议，是算法研究的顶级会议之一。2021 年，SODA 所收到的论文投稿为 637 篇，接收文章总量为 180 篇。

那么，彭泱是谁？

彭泱出生于江苏南京，2000 年随家人移民至加拿大。计算机与数学天赋极佳，八年级时参加十年级水平的美国数学比赛获得满分成绩，2004年与2005年获得加拿大计算机比赛金牌，2005年在第46届国际奥林匹克数学比赛中摘获银牌，同年在第17届国际奥林匹克信息学比赛中获得金牌。

高中毕业后，他继续在数学与计算机的学习上保持优异成绩：

2006年至2009年在加拿大滑铁卢大学攻读数学学士学位，随后直博到卡内基梅隆大学攻读 CS 博士学位，师从 Gary L. Miller 教授（首次提出基于广义黎曼猜想的确定性算法），期间获得 2011 年微软研究博士奖学金，其博士论文“Algorithm Design using Spectral Graph Theory”获得 CMU SCS 杰出论文奖。

随后，2013年至2015年，他又在麻省理工学院数学系担任博士后研究员，师从 Jonathan A. Kelner 教授。

2015年8月，彭泱加盟佐治亚理工学院计算机科学学院担任助理教授，2019年2月获得 NSF 教职奖。2016年至2018年期间曾在上海财经大学担任访问教授。他的研究兴趣主要是高效算法的设计、分析与执行。

在好友蒋炎岩（南京大学CS博士，获得2019年 CCF 优秀博士学位论文奖）的眼里，彭泱“是个非常神奇的人物：记忆力超强、解题速度超快、受到的训练超好。”

在接受 QuantaMagazine 的采访中，彭泱表示：“（在这个思路里），你可以猜测求解的过程，且没有老师会为此责备你。”

1 研究背景

线性方程组是计算领域最基本的问题之一。线性方程组一般包含两个或多个带有变量的方程式。这些变量表示事物之间相互联系的不同方式。这些方程式之所以被称为“线性”，是因为所有变量的幂恰好是 1，且方程式的图形解能形成一个平面。

线性方程组的一个常见案例是：在一个装满鸡和兔的笼子里，如果你只知道所有鸡和兔的头有 10 个，脚有 30 只，那么这个仓库里有多少只鸡、多少只兔？这也是我们小学就熟悉的“鸡兔同笼”问题。

由于很多时候鸡和兔的数量并不多，我们也可以靠猜测试出答案，然后在老师收卷子的时候悄悄藏起草稿纸。

或许很多同学都在那时候心存侥幸，估计内心也以为这个问题并不难。直到有一天，大学线性代数课的老师抛出了这样一个问题：

在诺亚方舟上船登记中，有1000种动物，所有动物有1023个头，6566只脚，1254只角，25098颗牙齿，356对翅膀，3487对触角，200万亿根毛发......（以上共1000种属性），请问每种动物的数量。

才发现，小学老师也是用心良苦，自己真是很傻很天真。好不容易顿悟之后，又在今天看着别人靠“猜测”发论文拿最佳论文奖，更是怀疑人生......

言归正传，线性方程组的应用当然远远不止于计算鸡与兔乃至全世界所有动物的数量。它可以在许多实际场景中应用，比如建一条更坚固的桥梁，或造一架更隐蔽的飞机，这些工作可能都需要求解数百万个相互依赖的线性方程组。

线性方程组是现代计算的主力军。从根本上说，线性方程组是对许多计算机科学的问题进行优化，这些问题主要是在约束系统内为一组变量寻找最佳值。如果我们可以更快地求解出线性方程组，那么我们也可以更快地解决这些计算机科学问题。

彭泱及其合作者所提出的新证明避开了以往求解方程组常用的矩阵乘法（matrix multiplication）。矩阵乘法限制了先前求解线性方程组的速度，因此，尽管如今矩阵乘法在求解线性方程组中仍发挥作用，但更多是扮演辅助的角色。彭泱等人将矩阵乘法与新的方法相结合，本质上是一种经过训练的预测解答。

他们用于求解线性方程组的方法的计算步骤是n^2.332，而线性代数教科书中的经典方法的计算步骤是n^3。这个结果的意义有多大呢？假设要求解一个1000变量的线性方程组，或者说“诺亚方舟上的鸡兔同笼问题”，经典方法需要10亿步，而他们提出的方法只需要约1000万步，只相当于前者的1%。随着变量数的增加，其加速效果也越显著。

2 笼子数学

回到前面所说的“笼子问题”。换个说法：假如农场里有鸡、独角犀牛和双角山羊，通过快速计算，你确定有 12 个头、38 只脚与 10 个角，请问每种动物分别有多少只？

在求解问题的过程中，为每只动物分配一个变量（c 代表鸡，r 代表犀牛，g 代表山羊），并为每一个属性（头、脚、角）写下一个方程式。每个变量前面的数字或系数代表了每只动物拥有的该属性的数量。

这时，我们得到了 3 个方程式与 3 个未知数。

求解这些问题的方法之一是变换一个方程式，并代入其它两个方程式。例如，0c + 1r + 2g = 10 可以变为 r = 10 – 2g。然后，我们将 r 的值替换到其他两个方程式中，以此类推，直到方程式里只包含一个变量，这时你就可以精确得到该变量的值。重复此过程，利用已解决的变量来得出其它变量即可。

除了上面这个方法，还有另外一种更复杂的求解方法，就是建立一个矩阵，矩阵的项（entry）为方程式的系数。上述的三个方程式可以转变为如下矩阵：

接下来，我们用另一个矩阵来表示数量未知的鸡、犀牛和山羊。

最后，我们用第三个矩阵来表示在仓库里观察到的头、脚和角的数量。

我们可以将这三个矩阵组合成一个简单的线性方程组，其中，第一个矩阵乘以第二个矩阵的变量，等于第三个矩阵。这时，我们可以使用线性代数来求解第二个矩阵。

如果方程组有唯一解，我们可以利用克莱姆法则求出，这也是线性代数教材中必提的经典方法，它对于任意数量变量的线性方程式都适用。

无论是变换方程式（高斯消元法）还是采用矩阵方法，最终都将执行相同数量的计算步骤来解决问题。也就是说，它们的计算步骤是相同的，即方程中变量数量的立方（n^3）。在上述方程中，有三个变量，因此需要27个计算步骤。如果有4种动物，则要求解它们需要64个步骤。如果有100种动物，则需要100万个步骤。对于工程问题中数百万变量的线性方程而言，其计算步骤更是天文数字。

在过去的50年中，研究人员一直致力于发现更有效地执行此过程的方法。通常，他们可以采用一些捷径（重用或合并操作的方式），从而可以用更少的步骤求解线性系统。

1969年，德国数学家 Volker Strassen 设计了一种仅以 n^2.81 个步骤来执行矩阵乘法的算法。自此之后，数学家和计算机科学家开始争相降低指数。来自麻省理工学院的副教授 Virginia Vassilevska Williams 和哈佛大学的博士后研究员 Josh Alman 于去年 10 月在这方面取得了最新进展，证明可以以 n^2.37286 个步骤执行矩阵乘法，相比法国数学家 Le Gall 在 2014 年得到的结果（此前被认为是最好的结果）的指数下降了0.00001。

上述种种均表明：任何线性系统的求解都可以简化为一个矩阵乘法的问题。目前为止，在理论上，矩阵乘法至少可以以 n^2.37286 的步骤执行。

但是，各种技术特征表明，求解线性系统的速度可能更快，也许只需要n^2步骤。我们使用矩阵乘法，是因为它是目前可用的最佳工具，但并不意味着不存在更好的工具。

据彭泱介绍：“如果你有一个装满计算机的房间，那么基于矩阵的算法便能够顺利地运算出有 50 个变量的方程组。现代数据的最大差异之一是该矩阵会变得非常大：不是 50x50，而是 10 亿 x 10 亿。大多项是以 0 开头，因此，由于存储限制，写下密集的矩阵（例如逆矩阵）通常不可行。”

彭泱的合作者 Vempala 表示：“求解线性系统这一问题没有理由要依赖于矩阵乘法的改进。”

图注：Santosh Vempala是佐治亚理工学院的计算机科学杰出教授，主要研究领域是算法、随机算法、计算几何和计算学习理论。他曾获得古根海姆奖、斯隆研究奖，并在2015年因“对凸集和概率分布算法的贡献”入选ACM Fellow。

彭泱和 Vempala 证明了他们的算法能够以 n^2.332 的计算步骤（计算复杂度）求解任何稀疏线性系统。这比矩阵乘法的最佳算法（n^2.37286）的指数快了四十分之一。对矩阵乘法进行渐进处理对于实际应用而言不会很快产生影响，但是作为一个概念证明，这种轻微的改进还是带来了很明显的进展：它表明存在一种求解线性系统的更好的方法。Vempala 说：“从哲学上讲，我们之前不知道是否可以比矩阵乘法更快，但现在我们知道了。”

还是以求解 1000 个变量的线性方程组为例，彭泱和 Vempala 的方法需要约 1000 万步，Volker Strassen 的方法需要约 2 亿 7 千万步，Virginia Vassilevska Williams 和 Josh Alman的方法需要约1300万步。

3 猜答案

要了解新的改进工具，我们需要了解另一种求解线性系统的既定方法。这是一种直观的方法，当遇到一群混淆在一起的鸡、犀牛和山羊时：对每个物种猜一个数，将它们插入等式中，看看离正确答案有多远，然后再猜一次。

这种“迭代方法”是工程师和科学家经常采用的。它可以很好地解决许多实际问题，因为专家通常不会盲目猜测，从而减少了猜测的次数。彭泱说：“对于现实世界中的科学计算问题，人类对答案通常具有很好的直觉。”

迭代方法在直觉可以提供某些支持的特定情况下很有用。当尝试求解的线性系统中包含大量系数为零的变量时，它们通常也会更有用。

在农场案例中，这种方法是很有用的。在此案例中，最容易直接求解的属性是角。为什么？因为鸡没有角，从而将涉及三只动物的问题减少到实际上涉及两只动物的问题。一旦摆脱了困境，就可以使用该信息快速求解脚和头的问题。

在更复杂的线性系统中，这种关系（即并非所有属性都与所有变量都有关）普遍存在。方程式可能有数百万个变量和数百万个方程式，但是每个方程式可能只涉及少量变量。这些类型的线性系统称为“稀疏”，意味着大多数方程中大多数变量取零值。现实世界的线性系统中经常会出现这种情况。这是迭代方法可以击败矩阵乘法的关键。Williams说：“只有当矩阵足够稀疏时，它才起作用。”

但是在进行这项新工作之前，没有人设法证明对于所有稀疏线性系统，迭代方法总是比矩阵乘法快。

4 协调随机性

彭泱和Vempala的新技术采用了迭代猜测策略的增强版本：他们的算法不仅可以进行单次猜测，而且可以并行进行多个猜测。这种方法可以加快搜索速度，就像一眼看到很多人一样。Giesbrecht说：“并行是魔法背后的秘密。”

论文地址：https://arxiv.org/pdf/2007.10254.pdf

一次进行多个猜测似乎是有用的，但是要使该策略起作用并不是那么简单。新算法的有效性在很大程度上取决于如何明智地进行引发迭代过程的初始猜测，以及寻找将并行猜测的结果组合成单个最终答案的巧妙方法。

回到农场的案例，该算法可能会首先进行三个初始猜测，其中每个猜测都是一个3×1矩阵，该矩阵指定了鸡、犀牛和山羊的数量。该算法将观察每个猜测和正确答案之间的差距，然后进行更多猜测，持续进行并行猜测线程。

该算法最终成功的关键在于，它会随机进行三个初始猜测。随机性可能对于猜测而言不是良好的起点，但作为一种通用方法，它具有独特优势，尤其是在处理大量问题时。也就是说，随机性可确保算法不会最终使搜索偏向问题的某一部分（从而有可能忽略实际解决方案所在的空间）。

彭泱说：“我需要确保所有的猜测都是足够随机的，以便它们涵盖所有可能的组合。猜测是一种非常糟糕的方法，但随着问题变得越来越大，它最终成为首选。”

在彭泱和Vempala的论文中，许多艰巨的技术工作都涉及证明随机猜测的不同部分也可以协同工作，包括实际上是最终答案的任何特定猜测。“存在协调的随机性，” Vempala说。

这意味着随机猜测不仅可以包含猜测本身的确切值，还可以涵盖介于两者之间的所有潜在猜测。这类似于两个人在森林中搜寻并不仅仅是搜寻他们所走的地面，还覆盖了他们视野内的区域。Vempala说：“两个 [猜测] 之间的所有内容也都包括在内。”

此搜索功能可确保算法将在某处找到答案，但是它本身并不能识别答案。为此，彭泱和Vempala必须做额外的证明。

该算法将随机猜测作为矩阵中的条目进行追踪。在矩阵条目中寻找答案使问题变成了矩阵乘法的问题，这当然是他们要规避的障碍。但是在这里，他们再次利用了随机性。

因为矩阵中的条目是随机的，并且它们之间发生协调，所以矩阵本身最终会具有某些对称性。这些对称性使快捷计算快捷成为可能。就像任何高度对称的对象一样，只需要知道其一部分，就可以推断出整体。

结果，彭泱和Vempala的算法可以比没有对称性的矩阵更快地在矩阵中找到解。矩阵的对称性也传达了另一个重要的好处：有助于确保猜测永远不会太大（导致以算法效率的角度来看变得难以理解）。彭泱说：“在进行猜测和协调时，我们必须控制数字的大小。”

参考链接：

1. https://www.quantamagazine.org/new-algorithm-breaks-speed-limit-for-solving-linear-equations-20210308/
2. http://www.chinaqw.com/node2/node2796/node2882/node3156/userobject6ai253919.html
3. https://www.cc.gatech.edu/news/642724/linear-systems-research-wins-soda-best-paper-award
4. https://www.cc.gatech.edu/~rpeng/