超级数学原理图解 新算法打破线性方程组的求解速度极限

作者：Kevin Hartnett，量子杂志高级作家 2021-3-8 译者：zzllrr小乐 2021-3-12

小学生很可能熟悉数学老师告诫他们不要仅仅猜出问题的答案。但是，有一个新的证明表明，实际上，正确的猜测有时是求解线性方程组（数学中的基础计算之一）的最佳方法。

该证明结果确立了第一种能够超越以前解决此类问题的速度硬性限制。

滑铁卢大学的Mark Giesbrecht说：“这是计算中最基本的问题之一。” “现在有一个我们可以走得更快的证明。”

乔治亚州理工学院的Richard Peng和Santosh Vempala的新方法于7月份线上发布，并于1月在年度ACM-SIAM离散算法研讨会上进行了介绍，并获得了最佳论文奖。

线性系统包含两个或更多个方程式，这些方程式具有变量，这些变量指定事物之间相互关联的不同方式。它们是“线性的”，因为唯一允许的幂恰好是1，方程解的图像形成平面。

线性系统的一个常见示例（数学学生可能也很熟悉）涉及一个装满鸡和猪的畜棚。如果你只知道有10个头和30只脚，那请问有几只鸡，几头猪？随着代数学生的学习，有一个确定的过程可以解决这个问题：写下两个代数方程并一起求解。

但是线性系统不仅仅可以算鸡和猪。它们出现在许多实际的环境中，在这些环境中，建造更坚固的桥梁或更隐形的飞机可能需要解决具有数百万个相互依赖的线性方程组的系统。从根本上说，线性系统是计算机科学中许多基本优化问题的特征，这些问题涉及在约束系统内为一组变量寻找最佳值。如果我们可以更快地求解线性系统，那么也可以更快地解决那些问题。

“线性系统是现代计算的老黄牛，” Vempala说。

新的证明通过避开该过程中通常使用的一种主要技术，找到了一种解决大型线性系统的更快方法。以前，这种称为矩阵乘法的技术对解决线性系统的速度设置了严格的速度限制。它仍然在工作中发挥着作用，但起补充作用。作者将其与一种新方法相结合，从本质上讲，这是一种经过训练的占卜方式。

“你可以猜测求解的方式，” Peng说。而且没有老师会为此生你的气。

畜棚数学

要了解线性系统以及如何解决它们，请回到畜棚，但可以想象现在里面是一群野生动物：鸡，独角犀牛和两只角的山羊。你可以快速数一下，确定有12个头，38只脚和10个角。你能弄清楚每只动物有多少只吗？

要计算的话，请为每只动物分配一个变量（c代表鸡，r代表犀牛，g代表山羊），并为每个属性编写一个方程式。每个变量前面的数字或系数反映了每只动物拥有的该属性的数量。

c r g = 12个头

2 c 4 r 4 g = 38只脚

0 c 1 r 2 g = 10只角

现在你有了三个方程式和三个未知数。

解决这些问题的一种方法是操纵一个方程式，并根据其他两个方程式定义一个变量。例如，0 c 1 r 2 g = 10变成r = 10 – 2 g。用其他两个方程式将该值替换为r，然后像这样继续进行，直到你仅使用一个变量定义出所有变量，然后就可以精确求解。然后，可以重复执行此过程，利用已解出的一个变量解决下一个问题。

但是另一种更复杂的处理方式是创建一个矩阵，其元素为方程式的系数。这三个方程变成了这个矩阵。

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

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

我们可以将这三个矩阵组合成一个线性系统，其中第一个矩阵乘以第二个矩阵的未知值等于第三个矩阵-在这一点上，我们可以使用线性代数求解第二个矩阵。

无论你是操纵方程式还是走矩阵路线，最终都将执行相同数量的计算步骤来解决这个问题。该数量是系统中变量数量的立方（n ³）。在本例中，我们有三个变量，因此需要3³（即27）个计算步骤。如果我们有四个动物和四个方程，将需要4³（即64）个步骤来求解它们。

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

Santosh Vempala

照片由佐治亚理工大学计算机学院提供

1969年，Volker Strassen设计了一种仅以n².⁸¹步执行矩阵乘法的算法。从那以后，数学家和计算机科学家开始争相降低指数。最近的进展（由去年10月麻省理工学院的Virginia Vassilevska Williams和哈佛大学的博士后研究员Josh Alman）证明，有可能以n².³⁷²⁸⁶步执行矩阵乘法。

所有这一切的结果是，你想要求解的任何线性系统都可以简化为关于矩阵乘法的问题，到目前为止，矩阵乘法理论上最少可用n².³⁷²⁸⁶个步骤执行。

但是各种技术特征表明，应该可能有比这更快的速度求解线性系统-可能需要n²个步骤。我们使用矩阵乘法是因为它是目前最好的工具，但这并不意味着没有更好的工具可以被发现。

Vempala说：“解决线性系统这一问题没有理由依赖于矩阵乘法的改进。”

猜测解

要了解新的改进工具，你需要牢记另一种确定线性系统的既有方法。这是一种可能会达到目标的直观方法，当你第一次遇到一群鸡，犀牛和山羊时，将每个数字猜一下，将它们插入方程中，看看情况，然后再猜一次。

这种“迭代方法”是工程师和科学家经常采用的方法。它对于许多实际问题都非常有效，因为专家通常不会盲目猜测，从而减少了在找到解之前需要进行的反复猜测。

彭说：“对于现实世界中的科学计算问题，人类对答案应该具有很好的直觉。”

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

在这个畜棚例子中，就很有用。最容易解决的属性是角。为什么？因为鸡没有角，这使鸡的那一项归零，并将涉及三只动物的问题化简为实际上只涉及两只动物的问题。一旦你解出角数，就可以使用该信息快速解决脚和头的问题。

在更复杂的线性系统中，这种关系（其中并非所有属性与所有变量都有关）可以普遍存在。你可能有数百万个变量和数百万个方程式，但是每个方程式可能只包含少量整体变量。这些类型的线性系统称为“稀疏的”，反映了大多数方程中大多数变量取零值的方式。在现实世界的线性系统中经常会出现这种情况。这是一种迭代方法可以击败矩阵乘法的情况。

Peng和Vempala解决线性方程组的新方法涉及进行随机但协调的猜测，然后从那里开始寻找解。

Terence Rushin提供照片

Williams说：“只有当矩阵足够稀疏时，它才起作用。”

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

协调的随机性

Peng和Vempala的新技术采用了迭代猜测策略的增强版本：他们的算法不仅可以进行单个猜测，而且可以并行进行许多猜测。这种方法可以加快搜索速度，就像在森林中找宝石，如果一次有很多人会找得更快。

Giesbrecht说：“并行是神奇所在。”

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

回到那个畜棚的示例，该算法可能会进行三个初始猜测，其中每个猜测都是一个3×1矩阵，该矩阵指定了鸡，犀牛和山羊的数量。该算法将观察每个猜测有多远，然后进行更多猜测，继续并行猜测线程。

该算法最终成功的关键是它会随机进行三个初始猜测。随机性似乎并不是猜测的良好基础，但作为一种通用方法，它具有优势，尤其是在处理大型问题时。也就是说，随机性确保你不会在搜索偏向问题的一部分时意外终止，从而有可能忽略实际解所在的空间。

彭说：“我需要确保我所有的猜测都是足够随机的，以便它们涵盖所有可能的组合。” “因为问题变得非常大时，意外终止于偏好的猜测方法是非常糟糕的。”

Peng和Vempala论文中的许多艰难的技术工作都涉及证明随机猜测的不同部分也可以协同工作，包括实际上就是问题解的任何特定猜测。

“存在协调的随机性，” Vempala说。

这意味着随机猜测不仅可以解释猜测本身的确切值，还可以涵盖介于两者之间的所有潜在猜测。这在本质上类似于两个人在森林中搜寻，并不仅仅是搜寻他们所走的地面，还覆盖了他们之间的整个视线。

Vempala说：“两个猜测之间的所有内容也都包括在内。”

此搜索功能可确保算法将在某处遇到解。但是它本身并不能确定解实际应是什么。为此，Peng和Vempala必须实际证明其它东西，来得到解。

该算法跟踪其随机猜测作为矩阵中的元素。在矩阵元素中寻找解成为一种矩阵乘法的问题，这当然是他们要规避的障碍。但是在这里，他们再次利用了随机性（随机生成矩阵元素）。

因为矩阵中的元素是随机的，它们之间有协调性，所以矩阵本身最终会具有某些对称性。这些对称性使计算捷径成为可能。就像任何高度对称的对象一样，你只需要知道它的一部分看起来是什么，就可以推断出整体。

结果，Peng和Vempala的算法可以比在具有相同元素数但没有有用对称性的矩阵中更快地在矩阵中找到解。矩阵的对称性也传达了另一个重要的好处：它们有助于确保猜测永远不会变得太大，以至于从算法效率的角度来看变得难以理解。

彭说：“在进行猜测和作协调时，我们必须控制出现的数字有多大。”

Peng和Vempala证明了他们的算法可以n ².³³²步求解任何稀疏线性系统。这比矩阵乘法的最佳算法（n ².³⁷²⁸⁶）快了约4%。险胜矩阵乘法对于任何时候的实际应用来说无关紧要，但是作为概念证明，这种轻微的改进是一个鸿沟：它表明完全存在一种求解线性系统的更好的方法。

Vempala说：“从哲学上讲，我们之前不知道是否可以比矩阵乘法更快。”

现在我们知道了。

,