399718奇闻趣事网majer 【奇闻趣事网】399718.com03.17 , 19:02
求解线性方程组：突破经典理论极限的最新算法
在数学上，线性就是指多元一次方程：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://***.quantamagazine.org/new-algorithm-breaks-speed-limit-for-solving-linear-equations-20210308/
本文版权归原作者，本站只做分享普及使用。若侵犯了你的权益，请提供版权有效证明，核实后下架删除。 (17)
未经允许不得转载：399718奇闻趣事网 » 求解线性方程组：突破经典理论极限的最新算法