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

在数学上,线性就是指多元一次方程: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/

0

更多精彩

Be the first to comment

Leave a Reply

Your email address will not be published.


*