有两位数学家最近找到了一种在计算机上求解大系统线性方程的方法，这一成果可以很快地用于诸多科学领域，如气象预测和建立经济模型。在这一进展中，这两位科学家重新解决了一个持续了五十年之久的难题。麻省理工学院的罗奈德 · 赖维斯特（Ronald Rivest）描述这项新的成果是“十分惊人的，它将使求解速度大大加快，看来很可能大大地推动这方面的实际工作”。此外，赖维斯特指出，这种方法在：理论上是很有意义的，他断言“这是一项真正的成果”。

这种方法是由纽约国立大学的维克多 · 潘（Victor Pan）和哈佛大学的约翰 · 里夫（John Reif）提出的。他们两人几个月前在一次讨论会上相遇并开始谈到更有效地求解线性系统的问题。此后，在一个周末潘去拜访里夫，他们找到了这个方法，这连他们自己都很惊讶。里夫回忆道：“这是非常令人兴奋的。”

线性系统是含有n个变量的n个方程的方程组，它是大规模计算中的最基本问题。它们极其难解并不是因为算法太难，而是因为它们是含有几千个变量的几千个方程。要找到所有这些变量的值，还要让这些值同时满足所有的线性方程。这项计算，不管怎么说都是艰巨的。事实上，气象科学家们曾开玩笑说，他们要花上三天时间解这些方程，以便得出明天天气如何的精确结论。

数学家们过去已经找到了两种不同的求解这些线性系统的方法。一种是直接求解法，如高斯消元法。这种解法至少可以追溯到19世纪60年代，德国数学家高斯。这种方法是，在解题过程的每一步消去一个变量。里夫说，“这种方法被普遍采用，它有精确的好处，但缺点是必须按顺序一步一步地进行”，这就意味着，解题过程的每一步都得按部就班不能同时进行以便提高速度。

另外，当科学家编制高斯消元法的程序放在计算机上运算时，就碰到了稳定性的问题。里夫解释道：“这儿有一个问题是，想得到一个满意的解，你应该在赋值时把小数点后的位数保留到第几位？高斯消元法使用有理数，但是计算机只保留有理数到某个精度，一种稳定的方法能在计算机的精确程度内给出解，但是高斯消元法却潜伏着不稳定性，因为在精确性上，甚至一个小小的误差都可能会像滚雪球一样被放大，结果就导致相当大的误差”。通常，计算机科学家对这个问题采用近似有理数的方法，用高斯消元法得到一个近似解来对付这个问题。然后，他们继续用第二种解线性方程的方法来修正这个解以达到他们所需的精度。

第二种解法包括一组技巧，即迭代法。它具有稳定、有效和可以平行进行的优点，这就是说，问题的许多步骤可以通过计算机同时平行进行计算。它们不存在固有的顺序。这种方法用对一个相应的n×n阶矩阵求逆的方法来求解一个线性系统。逆矩阵求得后，就可将矩阵相乘，容易地求出这个线性系统的解。

不过这种方法也有毛病，它们并不总能收敛于问题的解。里夫说：“一开头你就必须先用一个近似的逆矩阵，结果收敛与否就取决于最初的近似是否恰当。”

因此，通常是先用高斯消元法得到一个近似的逆矩阵，然后用迭代法直至得出问题的最终解。直接用其他方法求得近似的逆矩阵，再不断用迭代法求解会较容易些，但是没有人知道怎样才能使工作有效。不过人们曾一直试图这样做。

最早是德国数学家G. 舒尔茨提出了一种迭代法，即如果近似的逆矩阵已知的话，就可用此法直接求解。这篇论文于1933年发表。他表明，他的方法大约用log n步就可以给出问题的解。而其他的迭代法差不多需要n步。

然而，也许因为没有人找到一个求近似逆矩阵的好办法，所以舒尔茨的方法也不鲜为人知。每过十年左右，这个方法总是被重新提出一次。前不久，潘和里夫像其他人一样，重又发现了舒尔茨的方法，他们决定继续寻求有效地求近似逆矩阵的方法，这才使得这个已阻碍了研究者五十多年的“绊脚石”能得以扫除。

在此以前，求逆矩阵的最佳方法是1976年伯克利的加利福尼亚大学的L. 山奇（L. Csanky）发现的。山奇的方法大约只要(log n)²步，但它不稳定而且不能用在计算机上，因为它所需用于计算的处理机的数目大得不切实际。另一个研究者就设法减少了所需的处理机数量，但是这种方法仍不稳定。潘和里夫的方法所需处理机的数目仅仅是，用log n步乘两个n×n阶矩阵所需的处理机数。这个数目目前大约是n²，但是在理论上，它还可减少到n^2.5。此外，里夫认为，“这个方法在所有实际情况下都是成功的。”

里夫解释道，他在所需处理机数目上的改进，使他在寻求一个逆矩阵上达到了理论上的最佳时间。

潘和里夫还使他们的方法在求解一些普遍性问题时更为有效。在这些常见问题中，矩阵里有许多零，便变成了稀疏系统。有许多系统，例如天气预测和飞机机翼设计，都有这样的情况。当一个线性系统足够稀疏时，里夫和潘的方法使用的处理机远比稠密矩阵所用的处理机数要少。里夫说：“在理论上，你求得一个解至少可以比以前快一个数量级。”

然而里夫又说，目前使用得最多的并联工作的处理机还远少于1000个，因而用新方法来提高速度比它可以做到的要较逊色，这仍然是个实质性的问题。但是，已经有了几个系统拥有大数量的处理机。如，电脑公司在马萨诸塞的剑桥的联机系统（Thinking Machine Inc.'s Connection Machine in Cambrige，Massachusetts）已拥有16，000台处理机。这个公司目前正在筹建一个有64，000台处理机的网络。其他几个公司，包括IBM公司，也声称他们要在近几年内建立一个有1，000台以上的处理机的网络。这样，由新的并联处理机加上新的方法，寻求原线性系统的解的过程将会更快。里夫提到，天气预测的方程将会很容易解得。总之，里夫肯定：“这个可能性看来是十分令人兴奋的。”

[Science，1985年6月]