2021年3月9日 (二) 11:18 明华

2021-03-09T11:18:17Z

2021年3月9日 (二) 11:17 明华

2021-03-09T11:17:40Z

明华：创建页面，内容为“[https://m.toutiaocdn.com/i6937520960589414926/?app=news_article×tamp=1615287764&use_new_style=1&req_id=2021030919024401013516407147045486&group_id=693752096058...”

2021-03-09T11:16:51Z

创建页面，内容为“[https://m.toutiaocdn.com/i6937520960589414926/?app=news_article&timestamp=1615287764&use_new_style=1&req_id=2021030919024401013516407147045486&group_id=693752096058...”

新页面

[https://m.toutiaocdn.com/i6937520960589414926/?app=news_article&timestamp=1615287764&use_new_style=1&req_id=2021030919024401013516407147045486&group_id=6937520960589414926&wxshare_count=1&tt_from=weixin&utm_source=weixin&utm_medium=toutiao_android&utm_campaign=client_share&share_token=948dcff2-5952-4d1d-b0e4-8e0dc8a5ce94 打破线性方程求解速度极限，华人学者新算法获顶会最佳论文奖]

@@ 第1行： / 第1行： @@
-量子位
+量子位 2021.3.8
-小时前 · 量子位官方账号 优质科技领域创作者
+ · 量子位官方账号 优质科技领域创作者
-关注
 鱼羊 萧箫 发自 凹非寺
 量子位 报道 | 公众号 QbitAI

←上一版本		2021年3月9日 (二) 11:17的版本
第1行：		第1行：
		+	量子位
		+	5小时前 · 量子位官方账号优质科技领域创作者
		+	关注
		+	鱼羊萧箫发自凹非寺
		+	量子位报道 \| 公众号 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
		+
		+	— 完 —
		+	----
	[https://m.toutiaocdn.com/i6937520960589414926/?app=news_article&timestamp=1615287764&use_new_style=1&req_id=2021030919024401013516407147045486&group_id=6937520960589414926&wxshare_count=1&tt_from=weixin&utm_source=weixin&utm_medium=toutiao_android&utm_campaign=client_share&share_token=948dcff2-5952-4d1d-b0e4-8e0dc8a5ce94 打破线性方程求解速度极限，华人学者新算法获顶会最佳论文奖]		[https://m.toutiaocdn.com/i6937520960589414926/?app=news_article&timestamp=1615287764&use_new_style=1&req_id=2021030919024401013516407147045486&group_id=6937520960589414926&wxshare_count=1&tt_from=weixin&utm_source=weixin&utm_medium=toutiao_android&utm_campaign=client_share&share_token=948dcff2-5952-4d1d-b0e4-8e0dc8a5ce94 打破线性方程求解速度极限，华人学者新算法获顶会最佳论文奖]

打破线性方程求解速度极限，华人学者新算法获顶会最佳论文奖 - 版本历史

2021年3月9日 (二) 11:18 明华

2021年3月9日 (二) 11:17 明华

明华：创建页面，内容为“[https://m.toutiaocdn.com/i6937520960589414926/?app=news_article×tamp=1615287764&use_new_style=1&req_id=2021030919024401013516407147045486&group_id=693752096058...”