作者| 陳彩嫻、青暮
在大多數同學的記憶裡，數學老師也許都說過這麼一句話：
“問題的答案不能靠猜！”
但是，近日，來自佐治亞理工學院的華人學者彭泱（Richard Peng）卻憑藉“迭代猜測”策略，提出了一種能夠更快求解線性方程組的方法，並因此獲得 2021 年演算法頂會 ACM-SIAM 的最佳論文獎！
線性方程組是數學領域的奠基計算命題之一。
去年 7 月，彭泱及其合作伙伴 Santosh Vempala 將一種求解線性方程組的新方法發表於 arXiv 上，今年 1 月在 ACM-SIAM 離散演算法專題研討會（ACM-SIAM Symposium on Discrete Algorithms，簡稱“SODA”）上展示，獲得同行的一致肯定。
自1990年來，SODA每年舉辦一次，舉辦時間通常在一月份。該會議由ACM演算法和計算理論特別興趣小組（SIGACT）和SIAM離散數學活動小組共同贊助，其形式更像是理論計算機科學會議，而不是數學會議，
是演算法研究的頂級會議之一。
2021 年，SODA 所收到的論文投稿為 637 篇，接收文章總量為 180 篇。
那麼，彭泱是誰？
彭泱出生於江蘇南京，2000 年隨家人移民至加拿大。計算機與數學天賦極佳，八年級時參加十年級水平的美國數學比賽獲得滿分成績，2004年與2005年獲得加拿大計算機比賽金牌，
2005年在第46屆國際奧林匹克數學比賽中摘獲銀牌，同年在第17屆國際奧林匹克資訊學比賽中獲得金牌。
高中畢業後，他繼續在數學與計算機的學習上保持優異成績：
2006年至2009年在加拿大滑鐵盧大學攻讀數學學士學位，隨後直博到卡內基梅隆大學攻讀 CS 博士學位，師從 Gary L。 Miller 教授（首次提出基於廣義黎曼猜想的確定性演算法），期間獲得 2011 年微軟研究博士獎學金，其博士論文“Algorithm Design using Spectral Graph Theory”獲得 CMU SCS 傑出論文獎。
隨後，2013年至2015年，他又在麻省理工學院數學系擔任博士後研究員，師從 Jonathan A。 Kelner 教授。
2015年8月，彭泱加盟佐治亞理工學院計算機科學學院擔任助理教授，2019年2月獲得 NSF 教職獎。2016年至2018年期間曾在上海財經大學擔任訪問教授。他的研究興趣主要是高效演算法的設計、分析與執行。
在好友蔣炎巖（南京大學CS博士，獲得2019年 CCF 優秀博士學位論文獎）的眼裡，
彭泱“是個非常神奇的人物：記憶力超強、解題速度超快、受到的訓練超好。”
在接受 QuantaMagazine 的採訪中，彭泱表示：
“（在這個思路里），你可以猜測求解的過程，且沒有老師會為此責備你。”
1
研究背景
線性方程組是計算領域最基本的問題之一。線性方程組一般包含兩個或多個帶有變數的方程式。這些變量表示事物之間相互聯絡的不同方式。這些方程式之所以被稱為“線性”，是因為所有變數的冪恰好是 1，且方程式的圖形解能形成一個平面。
線性方程組的一個常見案例是：在一個裝滿雞和兔的籠子裡，如果你只知道所有雞和兔的頭有 10 個，腳有 30 只，那麼這個倉庫裡有多少隻雞、多少隻兔？這也是我們小學就熟悉的“雞兔同籠”問題。
由於很多時候雞和兔的數量並不多，我們也可以靠猜測試出答案，然後在老師收卷子的時候悄悄藏起草稿紙。
或許很多同學都在那時候心存僥倖，估計內心也以為這個問題並不難。直到有一天，大學線性代數課的老師丟擲了這樣一個問題：
在諾亞方舟上船登記中，有1000種動物，所有動物有1023個頭，6566只腳，1254只角，25098顆牙齒，356對翅膀，3487對觸角，200萬億根毛髮……（以上共1000種屬性），請問每種動物的數量。
才發現，小學老師也是用心良苦，自己真是很傻很天真。好不容易頓悟之後，又在今天看著別人靠“猜測”發論文拿最佳論文獎，更是懷疑人生……
言歸正傳，線性方程組的應用當然遠遠不止於計算雞與兔乃至全世界所有動物的數量。它可以在許多實際場景中應用，比如建一條更堅固的橋樑，或造一架更隱蔽的飛機，這些工作可能都需要求解數百萬個相互依賴的線性方程組。
線性方程組是現代計算的主力軍。
從根本上說，線性方程組是對許多計算機科學的問題進行最佳化，這些問題主要是在約束系統內為一組變數尋找最佳值。
如果我們可以更快地求解出線性方程組，那麼我們也可以更快地解決這些計算機科學問題。
彭泱及其合作者所提出的新證明避開了以往求解方程組常用的矩陣乘法（matrix multiplication）。矩陣乘法限制了先前求解線性方程組的速度，因此，儘管如今矩陣乘法在求解線性方程組中仍發揮作用，但更多是扮演輔助的角色。
彭泱等人將矩陣乘法與新的方法相結合，本質上是一種經過訓練的預測解答。
他們用於求解線性方程組的方法的計算步驟是n^2。332，而線性代數教科書中的經典方法的計算步驟是n^3。
這個結果的意義有多大呢？假設要求解一個1000變數的線性方程組，或者說“諾亞方舟上的雞兔同籠問題”，經典方法需要10億步，而他們提出的方法只需要約1000萬步，只相當於前者的1%。隨著變數數的增加，其加速效果也越顯著。
2
籠子數學
回到前面所說的“籠子問題”。換個說法：假如農場裡有雞、獨角犀牛和雙角山羊，透過快速計算，你確定有 12 個頭、38 只腳與 10 個角，請問每種動物分別有多少隻？
在求解問題的過程中，為每隻動物分配一個變數（c 代表雞，r 代表犀牛，g 代表山羊），併為每一個屬性（頭、腳、角）寫下一個方程式。每個變數前面的數字或係數代表了每隻動物擁有的該屬性的數量。
這時，我們得到了3 個方程式與 3 個未知數。
求解這些問題的方法之一是變換一個方程式，並代入其它兩個方程式。例如，0c + 1r + 2g = 10 可以變為 r = 10 – 2g。然後，我們將 r 的值替換到其他兩個方程式中，以此類推，直到方程式裡只包含一個變數，這時你就可以精確得到該變數的值。重複此過程，利用已解決的變數來得出其它變數即可。
除了上面這個方法，還有另外一種更復雜的求解方法，就是建立一個矩陣，矩陣的項（entry）為方程式的係數。上述的三個方程式可以轉變為如下矩陣：
接下來，我們用另一個矩陣來表示數量未知的雞、犀牛和山羊。
最後，我們用第三個矩陣來表示在倉庫裡觀察到的頭、腳和角的數量。
我們可以將這三個矩陣組合成一個簡單的線性方程組，其中，第一個矩陣乘以第二個矩陣的變數，等於第三個矩陣。這時，我們可以使用線性代數來求解第二個矩陣。
如果方程組有唯一解，我們可以利用克萊姆法則求出，這也是線性代數教材中必提的經典方法，它對於任意數量變數的線性方程式都適用。
無論是變換方程式（高斯消元法）還是採用矩陣方法，最終都將執行相同數量的計算步驟來解決問題。也就是說，它們的計算步驟是相同的，即方程中變數數量的立方（n^3）。在上述方程中，有三個變數，因此需要27個計算步驟。如果有4種動物，則要求解它們需要64個步驟。如果有100種動物，則需要100萬個步驟。對於工程問題中數百萬變數的線性方程而言，其計算步驟更是天文數字。
在過去的50年中，研究人員一直致力於發現更有效地執行此過程的方法。通常，他們可以採用一些捷徑（重用或合併操作的方式），從而可以用更少的步驟求解線性系統。
1969年，德國數學家 Volker Strassen 設計了一種僅以 n^2。81 個步驟來執行矩陣乘法的演算法。自此之後，數學家和計算機科學家開始爭相降低指數。來自麻省理工學院的副教授 Virginia Vassilevska Williams 和哈佛大學的博士後研究員 Josh Alman 於去年 10 月在這方面取得了最新進展，證明可以以 n^2。37286 個步驟執行矩陣乘法，相比法國數學家 Le Gall 在 2014 年得到的結果（此前被認為是最好的結果）的指數下降了0。00001。
上述種種均表明：
任何線性系統的求解都可以簡化為一個矩陣乘法的問題。
目前為止，在理論上，矩陣乘法至少可以以 n^2。37286 的步驟執行。
但是，各種技術特徵表明，求解線性系統的速度可能更快，也許只需要n^2步驟。我們使用矩陣乘法，是因為它是目前可用的最佳工具，但並不意味著不存在更好的工具。
據彭泱介紹：“如果你有一個裝滿計算機的房間，那麼基於矩陣的演算法便能夠順利地運算出有 50 個變數的方程組。現代資料的最大差異之一是該矩陣會變得非常大：不是 50x50，而是 10 億 x 10 億。大多項是以 0 開頭，因此，由於儲存限制，寫下密集的矩陣（例如逆矩陣）通常不可行。”
彭泱的合作者 Vempala 表示：
“求解線性系統這一問題沒有理由要依賴於矩陣乘法的改進。”
圖注：Santosh Vempala是佐治亞理工學院的計算機科學傑出教授，主要研究領域是演算法、隨機演算法、計算幾何和計算學習理論。他曾獲得古根海姆獎、斯隆研究獎，並在2015年因“對凸集和機率分佈演算法的貢獻”入選ACM Fellow。
彭泱和 Vempala 證明了他們的演算法能夠以 n^2。332 的計算步驟（計算複雜度）求解任何稀疏線性系統。這比矩陣乘法的最佳演算法（n^2。37286）的指數快了四十分之一。對矩陣乘法進行漸進處理對於實際應用而言不會很快產生影響，但是作為一個概念證明，這種輕微的改進還是帶來了很明顯的進展：它表明存在一種求解線性系統的更好的方法。Vempala 說：“從哲學上講，我們之前不知道是否可以比矩陣乘法更快，但現在我們知道了。”
還是以求解 1000 個變數的線性方程組為例，彭泱和 Vempala 的方法需要約 1000 萬步，Volker Strassen 的方法需要約 2 億 7 千萬步，Virginia Vassilevska Williams 和 Josh Alman的方法需要約1300萬步。
3
猜答案
要了解新的改進工具，我們需要了解另一種求解線性系統的既定方法。這是一種直觀的方法，當遇到一群混淆在一起的雞、犀牛和山羊時：對每個物種猜一個數，將它們插入等式中，看看離正確答案有多遠，然後再猜一次。
這種“迭代方法”是工程師和科學家經常採用的。它可以很好地解決許多實際問題，因為專家通常不會盲目猜測，從而減少了猜測的次數。彭泱說：“對於現實世界中的科學計算問題，人類對答案通常具有很好的直覺。”
迭代方法在直覺可以提供某些支援的特定情況下很有用。當嘗試求解的線性系統中包含大量係數為零的變數時，它們通常也會更有用。
在農場案例中，這種方法是很有用的。在此案例中，最容易直接求解的屬性是角。為什麼？因為雞沒有角，從而將涉及三隻動物的問題減少到實際上涉及兩隻動物的問題。一旦擺脫了困境，就可以使用該資訊快速求解腳和頭的問題。
在更復雜的線性系統中，這種關係（即並非所有屬性都與所有變數都有關）普遍存在。方程式可能有數百萬個變數和數百萬個方程式，但是每個方程式可能只涉及少量變數。這些型別的線性系統稱為“稀疏”，意味著大多數方程中大多數變數取零值。現實世界的線性系統中經常會出現這種情況。這是迭代方法可以擊敗矩陣乘法的關鍵。Williams說：
“只有當矩陣足夠稀疏時，它才起作用。”
但是在進行這項新工作之前，沒有人設法證明對於所有稀疏線性系統，迭代方法總是比矩陣乘法快。
4
協調隨機性
彭泱和Vempala的新技術採用了迭代猜測策略的增強版本：他們的演算法不僅可以進行單次猜測，而且可以並行進行多個猜測。這種方法可以加快搜索速度，就像一眼看到很多人一樣。Giesbrecht說：
“並行是魔法背後的秘密。”
論文地址：https：//arxiv。org/pdf/2007。10254。pdf
一次進行多個猜測似乎是有用的，但是要使該策略起作用並不是那麼簡單。新演算法的有效性在很大程度上取決於如何明智地進行引發迭代過程的初始猜測，以及尋找將並行猜測的結果組合成單個最終答案的巧妙方法。
回到農場的案例，該演算法可能會首先進行三個初始猜測，其中每個猜測都是一個3×1矩陣，該矩陣指定了雞、犀牛和山羊的數量。該演算法將觀察每個猜測和正確答案之間的差距，然後進行更多猜測，持續進行並行猜測執行緒。
該演算法最終成功的關鍵在於，它會隨機進行三個初始猜測。隨機性可能對於猜測而言不是良好的起點，但作為一種通用方法，它具有獨特優勢，尤其是在處理大量問題時。也就是說，隨機性可確保演算法不會最終使搜尋偏向問題的某一部分（從而有可能忽略實際解決方案所在的空間）。
彭泱說：“我需要確保所有的猜測都是足夠隨機的，以便它們涵蓋所有可能的組合。
猜測是一種非常糟糕的方法，但隨著問題變得越來越大，它最終成為首選。
”
在彭泱和Vempala的論文中，許多艱鉅的技術工作都涉及證明隨機猜測的不同部分也可以協同工作，包括實際上是最終答案的任何特定猜測。“存在協調的隨機性，” Vempala說。
這意味著
隨機猜測不僅可以包含猜測本身的確切值，還可以涵蓋介於兩者之間的所有潛在猜測。
這類似於兩個人在森林中搜尋並不僅僅是搜尋他們所走的地面，還覆蓋了他們視野內的區域。Vempala說：“兩個 ［猜測］ 之間的所有內容也都包括在內。”
此搜尋功能可確保演算法將在某處找到答案，但是它本身並不能識別答案。為此，彭泱和Vempala必須做額外的證明。
該演算法將隨機猜測作為矩陣中的條目進行追蹤。在矩陣條目中尋找答案使問題變成了矩陣乘法的問題，這當然是他們要規避的障礙。但是在這裡，他們再次利用了隨機性。
因為矩陣中的條目是隨機的，並且它們之間發生協調，所以矩陣本身最終會具有某些對稱性。
這些對稱性使快捷計算快捷成為可能。
就像任何高度對稱的物件一樣，只需要知道其一部分，就可以推斷出整體。
結果，彭泱和Vempala的演算法可以比沒有對稱性的矩陣更快地在矩陣中找到解。矩陣的對稱性也傳達了另一個重要的好處：有助於確保猜測永遠不會太大（導致以演算法效率的角度來看變得難以理解）。彭泱說：“在進行猜測和協調時，我們必須控制數字的大小。”
參考連結：
https：//www。quantamagazine。org/new-algorithm-breaks-speed-limit-for-solving-linear-equations-20210308/
http：//www。chinaqw。com/node2/node2796/node2882/node3156/userobject6ai253919。html
https：//www。cc。gatech。edu/news/642724/linear-systems-research-wins-soda-best-paper-award
https：//www。cc。gatech。edu/~rpeng/