求解线性方程组：突破经典理论极限的最新算法

在数学上，线性就是指多元一次方程：x+6y+17z+……+2.88t=0。替换未知变量——也就是小写的字母——前的系数，如果能得到其他的等式关系(亦即新的多元一次方程)，那我们就能联立出多元一次方程组。这种方程组可以看做是线性系统。

线性是数学研究中的核心内容之一。实际上，人类研究非线性系统的主要手段也是用线性系统“逐段逼近”，就像是我们用直线段去逼近曲线，好弄清曲线的性质一样。

线性概念，是全部应用数学的根基——说它是现代文明的根基也不算太夸大其词。单就线性规划这门应用学科，起码和现实世界里100亿美元的业务或产能相联系。

所以，一次方程组非常重要。

在数学实践中， 我们发现线性方程组的各种性质本质上来源于它们的一排排系数。如果把各项系数按照它们在方程组的位置排列出来，我们就得到了另一个数学上超级重大的概念——矩阵。

数学家非常巧妙地把求解方程组的过程，转化为矩阵运算。

在工业、商业、军事、航天和物理化学等科学计算中，最基本的问题就是求出变量很多的、有现实意义的线性方程组的数值解。

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

1969年，Volker Strassen设计出仅需要n^2.81步执行矩阵乘法的算法(n是方程组变量的规模)。从那以后，数学家和计算机科学家开始争相加入竞赛。麻省理工学院的Virginia Vassilevska Williams和哈佛大学的博士后研究员Josh Alman于去年10月取得了最新进展，证明可以以n^2.37286步执行矩阵乘法，是当前理论的最佳成果。

但是，有理论线索暗示，我们可在n^2步内执行矩阵乘法。

乔治亚州理工学院的Richard Peng和Santosh Vempala的开发出用于稀疏矩阵(矩阵里的元素以0为主)的迭代方法，初步证实了上面的猜测。他们于去年7月份在线发布(https://arxiv.org/abs/2007.10254)，并于今年1月在年度ACM-SIAM离散算法专题讨论会上正式发表，获得了最佳论文奖。

他们的方法另辟蹊径，引入了随机性，从随机的初始值开始迭代。他们从3个随机点开始，其中最巧妙的是，3点确定一个“三角区域”，他们的方法可以把区域里的可能值，用初始点“协调”出来。

理论上讲，新算法比之前最佳算法的效率还要高出4%——当然目前仅仅针对稀疏矩阵。虽然数字不大起眼，但这4%，相当于逾越了不可能的鸿沟——在哲学意义上开辟出了之前不存在的道路。

https://www.quantamagazine.org/new-algorithm-breaks-speed-limit-for-solving-linear-equations-20210308/