近日，来自佐治亚理工学院的华人学者彭泱（Richard Peng）却凭借“迭代猜测”策略，提出了一种能够更快求解线性方程组的方法，并因此获得 2021 年算法顶会 ACM-SIAM 的最佳论文奖！

论文地址：https://arxiv.org/pdf/2007.10254.pdf

线性方程组是数学领域的奠基计算命题之一。去年 7 月，彭泱及其合作伙伴 Santosh Vempala 将一种求解线性方程组的新方法发表于 arXiv 上，今年 1 月在 ACM-SIAM 离散算法专题研讨会（ACM-SIAM Symposium on Discrete Algorithms，简称“SODA”）上展示，获得同行的一致肯定。

自1990年来，SODA每年举办一次，举办时间通常在一月份。该会议由ACM算法和计算理论特别兴趣小组（SIGACT）和SIAM离散数学活动小组共同赞助，其形式更像是理论计算机科学会议，而不是数学会议，是算法研究的顶级会议之一。2021 年，SODA 所收到的论文投稿为 637 篇，接收文章总量为 180 篇。

彭泱出生于江苏南京，2000 年随家人移民至加拿大。2006年至2009年在加拿大滑铁卢大学攻读数学学士学位，随后直博到卡内基梅隆大学攻读 CS 博士学位，师从 Gary L. Miller 教授（首次提出基于广义黎曼猜想的确定性算法），期间获得 2011 年微软研究博士奖学金，其博士论文“Algorithm Design using Spectral Graph Theory”获得 CMU SCS 杰出论文奖。2015年8月，彭泱加盟佐治亚理工学院计算机科学学院担任助理教授，2019年2月获得 NSF 教职奖。他的研究兴趣主要是高效算法的设计、分析与执行。

彭泱及其合作者所提出的新证明避开了以往求解方程组常用的矩阵乘法（matrix multiplication）。矩阵乘法限制了先前求解线性方程组的速度，因此，尽管如今矩阵乘法在求解线性方程组中仍发挥作用，但更多是扮演辅助的角色。彭泱等人将矩阵乘法与新的方法相结合，本质上是一种经过训练的预测解答。

他们用于求解线性方程组的方法的计算步骤是n^2.332，而线性代数教科书中的经典方法的计算步骤是n^3。这个结果的意义有多大呢？假设要求解一个1000变量的线性方程组，或者说“诺亚方舟上的鸡兔同笼问题”，经典方法需要10亿步，而他们提出的方法只需要约1000万步，只相当于前者的1%。随着变量数的增加，其加速效果也越显著。

编者注：“诺亚方舟上的鸡兔同笼问题”。在诺亚方舟上船登记中，有1000种动物，所有动物有1023个头，6566只脚，1254只角，25098颗牙齿，356对翅膀，3487对触角，200万亿根毛发......（以上共1000种属性），请问每种动物的数量。

内容中包含的图片若涉及版权问题，请及时与我们联系删除