网易首页 > 网易号 > 正文 申请入驻

打破线性方程求解速度极限,华人学者新算法获顶会最佳论文奖

0
分享至

  

鱼羊 萧箫 发自 凹非寺
量子位 报道 | 公众号QbitAI

  还记得小时候被“鸡兔同笼”支配的恐惧吗?

  其实,当我们学习了二元一次方程,就知道这个问题并不复杂:

  

  不过,可别小看了这样的线性方程,试想一下,如果动物的种类不止2种,特征也不只头和脚呢?

  比如……

  

  这个时候,我们就只能求助矩阵乘法了。

  

  那么,问题来了,采用高斯消元法,求解的复杂度就是O(n3)

  也就是说,如果n从2增加到4,求解复杂度就会增加2³即8倍。

  n越来越大,计算的步骤就会以3次方的速度快速增加……

  想想机器学习、工程项目里极其复杂的矩阵乘法,是不是有点头皮发麻的感觉。

  好消息是,现在,这个困扰工程师们已久的基础问题,有了突破性进展。

  计算机理论顶会SODA 2021的最佳论文,用“猜”答案的方式,一口气把算法复杂度减小到了O(n2.3316)!

  论文作者,是来自佐治亚理工学院的两位数学家:彭泱和Santosh Vempala。

  

  这项研究具体是怎么一回事?快来一起研究研究。

  IOI金牌获得者,靠“猜”推动研究

  IOI金牌获得者、来自佐治亚理工学院的助理教授彭泱,和他的合作者Santosh Vempala共同提出了一种全新的思路。

  

  相比于此前,数学家们不停地改进矩阵乘法的算法,他们别出心裁,想到能否靠“”,来重新设计一种算法。

  这种方法就是:猜测每个未知数的值,把它们代入方程后,查看结果与实际值相差有多大。

  然后,修正未知数的值,再猜一次。

  这种方法,在计算机方向上被称为迭代法

  

  彭泱的这种迭代算法,在方程的数量变得极多、且每个方程涉及的未知数较少时,显示出了巨大的优势。

  也就是说,如果在一个系数矩阵属于“稀疏矩阵”——矩阵本身特别大,但相对地,系数为0的数量又非常多的时候,迭代法就会出现神奇的结果。

  

  此前,没有人能够证明,“迭代法”对于稀疏矩阵而言,是否会比“矩阵乘法”更快。

  当然,这种算法并不只靠“猜”。

  彭泱设计的算法中,他们还会在给出多组随机数的同时,将这些随机数组并行计算。

  这就像是数百个人同时在山林中搜索宝藏,肯定比一个人反复搜索要更快。

  但这种算法的设计,还面临两个难点:

  如何保证设计出来的数,足够随机、不偏向问题的任何一部分?

  如何保证设计出来的这些随机数组,全面覆盖每一种可能性?

  

  他们发现,正因为由随机数构造出的矩阵中,项数是随机的、且彼此之间有着某种关联,因此,这一矩阵本身就具有某种对称性。

  这就意味着,如果知道矩阵中某些具体的数值,就能推断出一整个矩阵的形状。

  这一发现,使得他们设计的算法,比未考虑矩阵对称性的那些算法,找到解的速度更快。

  事实证明,这种算法确实能够保证在O(n2.3316)复杂度以内,完成任何计算。

  这比之前的O(n2.37286),复杂度降低了不少,可以说是一个巨大的进步。

  

  这一新发现,让彭泱和他的合作者获得了ACM-SIAM离散算法研讨会SODA 2021的最佳论文奖。

  为什么要降低计算复杂度?

  解一个二元一次方程,也就是2×2的矩阵,靠中学知识就能轻松搞定。

  然而当n变得越来越大,求解方程的计算量就会以3次方的速度迅速增加。

  这是什么概念?

  意味着如果线性问题中,要求解的未知数达到100甚至10000,那么计算量复杂度就会增加1000000、甚至1012倍。

  目前,机器学习、动力学模拟等问题,都会遇到超大规模线性方程组,如何降低计算复杂度,一直是学者们致力于解决的问题。

  

  要是计算复杂度居高不下,对于计算机而言,将会是一个巨大而沉重的负担。

  因此,数学家们一直在想方设法将线性问题的复杂度弄得更小一点,也就是让O(nω)中的ω变小。

  哪怕ω减小的量只有0.00001,对于上百万未知数的方程组来说也是一个巨大的进步。

  通过不断改善矩阵乘法,ω先是从3降低到2.81,历经多次研究后,被MIT和哈佛的数学家们降低到2.37286。

  然而,到这个阶段,数学家们倾尽全力所设计的新算法,也只是将ω降低了0.00001而已。

  有数学家进行过预测,ω可以无限接近于2,也就意味着这种线性问题的计算复杂度还能尽力向O(n²)靠拢。

  因此,彭泱他们的新算法,可以说是将这一研究向前推动了一大步。

  关于作者

  论文作者彭泱,江苏南京人,现为佐治亚理工学院计算机科学系助理教授。

  他本科毕业于滑铁卢大学数学专业,其后在CMU拿下计算机科学博士学位。2013-2015年在MIT担任应用数学博士后。

  目前,他主要关注的研究方向是高效算法的设计、分析和实现。

  根据Google Scholar,彭泱的论文引用数为2788,h指数为28。

  

  他的名字,也频频见于FOCS、STOC、SODA等计算机理论顶会论文当中。

  

  彭泱与数学和计算机结缘很早,据中国侨网报道,他8年级时就曾参加10年级水平的美国数学比赛,并获得满分的成绩。还在2004年和2005年参加加拿大计算机竞赛,摘下金牌。

  2005年和2006年,彭泱代表加拿大队参加国际奥林匹克数学竞赛(IMO),分别获得银牌和铜牌。

  

  而在此期间,他还参与了2004、2005和2006年的国际奥林匹克信息学竞赛(IOI),并在2005年获得金牌。

  

  论文的另一位作者Santosh Vempala是著名计算机科学家,佐治亚理工学院计算机科学杰出教授。2015年,他入选“因对凸集和概率分布算法的贡献”入选ACM Fellow。

  

  他的主要研究方向是算法理论,用于抽样、学习、优化和数据分析的算法工具,高维几何,随机线性代数等。

  Santosh Vempala还是古根海姆奖、斯隆奖获得者。

  论文地址:

  https://arxiv.org/abs/2007.10254

  参考链接:

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

  [2]https://www.cc.gatech.edu/~rpeng/

  [3]http://www.arc.gatech.edu/

  [4]https://www.chinaqw.com/node2/node2796/node2882/node3156/userobject6ai253919.html

  [5]https://www.siam.org/conferences/cm/conference/soda21

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐

《浪姐2》成团不足一天,龚俊官宣,周笔畅跌落神坛,那英夺第一

八爪娱先锋
2021-04-15 19:36:17

NBA本世纪十大最糟糕选秀:本内特屈居第三,金童排第一

体育课副班长
2021-04-15 19:20:02

逼近-100度!舒力基台风冲破对流层,这是好事坏事?分析:坏事

中国气象爱好者
2021-04-15 23:47:24

一个中年男人的帕拉梅拉梦

购车之前
2021-04-15 22:36:53

辟谣:原油从63到70,油价涨了4毛,原油从70到63,油价只降1.8毛

每日油价
2021-04-15 07:09:08

高层发话了!A股反弹在即!透露两个机会(附股)

大嘴讲美食
2021-04-15 21:17:31

男子路遇流浪汉乞讨,掏出银行卡并告知密码:我给你200自己去取

社会报料
2021-04-14 20:41:28

姚明重磅决定!方硕沈梓捷均被禁赛,马布里回应下课,宏远大四喜

多特体育说
2021-04-15 22:24:58

成功瞒过全世界,中方亮出“底牌”,西方国家意识到问题严重性

环球新军事
2021-04-13 12:47:32

哈登要开心坏了!篮网要签下第七位球星,这下总冠军势在必得

开球咯
2021-04-15 21:52:30

苏州!惊曝世界级IP!数亿年轻人朝圣地!天空之城2077来了……

温文尔雅的于晓生
2021-04-15 07:35:27

印度摊上大事了,把变异病毒传给美国人,白宫恼怒不已:必须严惩

紫龙防务观察
2021-04-15 13:15:24

有困难找中国? 美国将寻求对华合作 普京与拜登通话商讨大事

张殿成
2021-04-15 14:33:40

王鸥前夫近照曝光,原来是大名鼎鼎的他,网友:难怪会看上刘恺威

社会de记忆
2021-04-14 10:05:07

为什么你连一瓶水都不能带上飞机?背后有个惊心动魄的故事

我们的百变生活
2021-04-15 01:21:23

拜登称撤军阿富汗集中应对中国挑战,奥巴马迅速发声,赵立坚表态

小杨同志
2021-04-15 23:06:49

当下热播剧大洗牌:《长歌行》跌出前三,榜首开播拿下收视第一!

在旅途找乐子
2021-04-14 16:27:26

不打仗了?美国、乌克兰向俄罗斯低头,普京却不给面子:别想骗我

环球风马牛
2021-04-15 11:17:23

一对“情人”的聊天记录遭曝光,太现实太打脸了!

民生观点
2021-04-14 15:40:49

市场上这5款伪豪车,在国内很抢手,在国外仅是普通买菜车

追彩虹的人
2021-04-14 20:47:58
2021-04-16 02:09:08
量子位
量子位
追踪人工智能动态
4772文章数 96807关注度
往期回顾 全部

科技要闻

美媒:英伟达不应该忘了普通游戏玩家

头条要闻

女子5年4次起诉离婚被驳:离婚是最大心愿

头条要闻

女子5年4次起诉离婚被驳:离婚是最大心愿

体育要闻

王霜:留洋没有表面看起来风光

娱乐要闻

刘诗诗穿宝蓝色长裙现身 气质温柔

财经要闻

汽车要闻

3.8秒破百/续航超700公里 ZEEKR 001今晚上市

态度原创

本地
房产
时尚
数码
公开课

本地新闻

30岁不结婚,丢脸吗?

房产要闻

又有2盘启动认筹 嘉泷汇4大拦客嫌疑 中环境秋月热情揽客 | 楼市包打听

张雨绮疑似新恋情被拍 男友是小8岁的帅哥提琴手

数码要闻

大疆发布DJI Air 2S:售6499元 1英寸大底/4方向避障

公开课

记者卧底精神病院,震惊发现正常人不在少数