新算法破坏求解线性方程的速度限制

等级学校数学学生可能熟悉教师劝告他们不要只是猜到问题的答案。但是，一个新的证据确定了，实际上，正确的猜测有时是解决线性方程系统的最佳方法，是数学的基岩计算之一。

因此，证据建立了能够超越先前对这些类型问题的速度难以解决的难度限制的第一种方法。

“这是计算中最基本的问题之一，”滑铁卢大学的马克·格斯布莱克说。 “现在我们有一个我们可以更快的证据。”

佐治亚理工学院Richard Peng和Santosh Vempala的新方法在7月份发布，并于1月份在ACM-Siam讨论会上发布了离散算法，赢得了最佳纸张奖。

线性系统涉及两个或多个方程，其中变量指定了彼此相关的不同方式。它们是“线性”，因为唯一的允许功率正好1，以及方程式的解决方案的图表。

线性系统的一个常见例子 - 也可能熟悉数学学生 - 涉及一个充满鸡和猪的稗子。如果你只知道有10头和30英尺，那里有多少只鸡，有多少猪？作为代数学生学习，有一个设置程序来弄清楚：写下两个代数方程并一起解决它们。

但是线性系统可以做的不仅仅是数鸡和猪。它们在许多实际设置中裁剪，建造一个坚固的桥梁或隐形飞机可以涉及用数百万相互依赖的线性方程来解决系统。更从根本上，线性系统在计算机科学中的许多基本优化问题中具有涉及在约束系统中找到一组变量的最佳值。如果我们可以更快地解决线性系统，那么我们也可以更快地解决这些问题。

新证据通过申请通常在该过程中使用的主要技术之一来求解大类线性系统的更快方式。该技术，称为矩阵乘法，先前设置了线性系统如何解决的快速限制。它仍然在工作中具有互补的作用。作者将其与一种新的方法耦合，实质上是一种训练有素的占歧视的形式。

“你可以猜出你的解决方案，”彭说。没有老师对此生气。

为了获得线性系统的感觉以及如何解决它们，返回稗，但想象现在是一个人的更多信息：鸡，1角犀牛和2角山羊。您可以快速计数，并确定有12个头部，38英尺和10个角。你能弄清楚每只动物有多少吗？

要继续，将变量分配给每只动物（用于Chickens，f for RoIn，Goats的R），并为每个属性写一个等式。每个变量前面的数字或系数反映了每个动物所拥有的该属性的数量。

解决它们的一种方法是操纵一个方程并根据其他两个来定义一个变量。例如，0 C + 1 r + 2 g = 10变成r = 10-2g。将该值替换为其他两个方程中的r，然后继续如此，直到您在只为一个变量中定义所有变量，然后您可以完全解决。然后，您可以重复该过程，利用您解决的一个变量来解决下一个变量。

但另一个，更复杂的方法是创建一个矩阵，其条目是方程的系数。三方程变成了该矩阵。

$ laTex \ left [\ begin {array} {ll} 1＆amp; 1＆amp; 1 \\ 2＆amp; 4＆amp; 4 \\ 0＆amp; 1＆amp; 2 \结束{array} \右] $

最后，我们代表了具有第三矩阵的观察到的头部，脚和角。

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

$ laTex \ left [\ begin {array} {ll} 1＆amp; 1＆amp; 1 \\ 2＆amp; 4＆amp; 4 \\ 0＆amp; 1＆amp; 2 \ end {array} \ revally] $×$ laTex \ left [\ begin {array} {ll} c \\ r \\ g \ nod {array} \ revally] $ = $ latex \ left [\ begin {array } {ll} 12 \\ 38 \\ 10 \ end {array} \右] $

无论您是操纵方程式还是采用矩阵路由，您将最终执行相同的计算步骤数来解决问题。该数字是系统中的变量数的多维数据集（n 3）。在这种情况下，我们有三个变量，因此需要3 3或27个计算步骤。如果我们有四只动物和四个方程，则需要4个3或64个措施来解决它们。

在过去的50年里，研究人员已经找到了更有效地执行此程序的方法。通常存在捷径，他们可以使用 - 重用或结合操作的方式 - 让它们以更少的步骤解决线性系统。

1969年，Volker Stassen设计了一种仅在N 2.81步骤中执行矩阵乘法的算法。从那时起，数学家和计算机科学家们已经进一步降低了指数。去年10月由弗吉尼亚州弗吉尼亚州弗吉尼亚理工学院威廉姆斯（Harvard University）的Massachusetts Tearch of Mastonectoral研究员Josh Alman威廉姆斯提出了最新的进展证明，可以在N 2.37286步骤中进行矩阵乘法，从0.00001的指数上进行改进以前最好的标记。

所有这些的结果是您要解决的任何线性系统都可以减少到关于矩阵乘法的问题，并且as现在，矩阵乘法至少可以理论上在n 2.37286步骤中执行。

但各种技术特征表明应该可以更快地解决线性系统 - 在可能的n步2步骤中。我们使用矩阵乘法，因为它是最好的可用工具，但这并不意味着没有更好的工具等待被发现。

“解决线性系统的这种问题没有理由取决于矩阵乘法的改进，”vempala说。

要了解新的和改进的工具，您需要记住另一种解决线性系统的方法。这是一个直观的一个，你可能会伸出一群鸡，你可以伸出一群鸡，犀牛崩溃和山羊的旅行都混合在一起：每个人的猜测数字，将它们插入方程式，看看你有多远，再次猜测。

这种“迭代方法”是工程师和科学家经常使用的“迭代方法”。它适用于许多实际问题，因为专家通常盲目地猜测，这在寻找解决方案之前，它们需要迭代猜测的数量。

“对于真实世界的科学计算问题，人类对答案应该是非常好的直觉，”彭说。

迭代方法在直觉可以提供一些支持的特定实例中是有用的。每当您尝试解决的线性系统具有大量变量时，它们也更加有用，其系数为零。

此功能是存在的 - 并且有用 - 在禁令示例中，在其中用于解决的最简单的属性是角。为什么？因为鸡没有角，其中零鸡术语，减少了一个涉及三只动物的问题，真正涉及两个。一旦你就可以使用那种信息来使用该信息来快速解决脚和头部。

在更复杂的线性系统中，这种关系，其中不是所有属性都属于所有变量，都可以普遍存在。您可能有数百万个变量以及数百万个方程，但每个方程式可能只涉及少数整体变量。这些类型的线性系统称为“稀疏”，反映大多数方程中大多数变量在大多数方程中取得零的方式。这是一个经常在现实世界的线性系统中出现的情况。它是迭代方法可以击败矩阵乘法的方法。

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

PENG和VEMPALA的新技术采用了迭代猜测策略的增强版本：而不是刚刚猜测，他们的算法并行猜测许多猜测。这种方法加速了搜索，就像你在森林中找到的宝石一样快速，如果你有许多人看到一次。

显而易见的是，立即编制多次猜测是有用的，但使战略工作并不是那么简单。新算法的有效性在很大程度上依赖于智能了解如何使迭代过程中的初始猜测以及找到将并行猜测的巧妙方式结合成单个最终答案的聪明方式。

要返回禁令示例，该算法可能会进行三个初始猜测，其中每个猜测是一个3×1矩阵，指定一些鸡，犀牛和山羊。该算法将观察每个猜测的距离，然后猜测更多猜测，继续并行猜测线程。

算法最终成功的关键是它使三个最初的猜测随机猜测。随机性可能看起来似乎不是猜测的良好基础，而是作为一种通用方法，它具有它的优势，特别是当你使用巨大的问题时。即，随机性确保您没有意外地最终偏向您的搜索到问题的一部分，可能会忽略实际解决方案所在的空间。

“我需要确保我的所有猜测都是充分的随机性，以便他们涵盖了所有可能的组合，”彭说。 “这是这种非常可怕的方式，使猜测最终成为优选的方法，因为这个问题变得非常大。”

彭和vempala论文的大部分艰难的技术工作都涉及证明随机猜测的不同股，包括任何特定的猜测，实际上是问题的答案。

这意味着随机猜测不仅考虑了猜测本身的确切值，还涵盖它们之间的所有潜在猜测。它的精神与两个人在森林中搜索的是类似的，这不仅仅是搜索他们走的地面;他们还涵盖了它们之间的全部视线。

此搜索功能可确保算法将遇到某处的解决方案。但它本身并不确定解决方案的实际情况。要做到这一点 - 实际上把手放在解决方案 - 彭和韦姆帕拉必须证明别的东西。

该算法在矩阵中的条目中跟踪其随机猜测。在矩阵中的条目中找到解决方案成为矩阵乘法的问题，当然是他们向规避的路障。但是，他们再次利用他们用于种子矩阵中的条目的随机性。

因为矩阵中的条目是随机的，并且在它们之间发生协调，因此矩阵本身最终有一定的对称性。那些对称性能够实现计算快捷方式。就像任何高度对称的对象一样，您只需要知道它的一部分是什么样的，以便推断整体。

因此，PENG和VEMPALA的算法可以在矩阵内的速度在矩阵中找到与具有相同数量的矩阵中的解决方案，但都没有有用的对称性。矩阵的对称也传达了另一个重要的好处：它们有助于确保猜测从未生长如此之大，从算法效率的角度变得笨重。

“我们不得不控制一个数字在做出这种猜测和协调时有多大，”彭说。

PENG和VEMPALA证明了他们的算法可以在N 2.332步骤中解决任何稀疏线性系统。 这击败了矩阵乘法（N.2.37286）的最佳算法的指数大约四百分点。 边缘矩阵乘法对于实际应用很快就无关紧要，而是作为概念证明，这种略微改善是一个鸿沟：它显示了解决线性系统的完全更好的方法。 “哲学上我们之前不知道如果你可以比矩阵乘法更快，”vempala说。