第九十章 秒掉莫斯科
第90章 秒掉莫斯科
莫斯科的清晨來得早。
六點半，天已經大亮。
陸沉睜開眼，腦海中的倒計時剛好歸零四個小時的睡眠，足夠恢復精力了。
林楓還在睡，呼吸均勻。
昨晚他在終端前待到十一點，反覆熟悉BESM—6的指令集，最後是被值班老師趕回來的。
陸沉沒有叫醒他。他安靜地洗漱，然後坐在床邊，閉上眼睛。
意識沉入那片他稱之為「構建空間」的領域。
這是他的超算大腦真正施展威力的地方。
在他的感知中，BESM—6的硬體結構像一張三維藍圖般展開。
寄存器組、內存分頁、指令預取隊列、微碼存儲器—每一個模塊都清晰可見，每一個信號傳遞的時序都精確到時鐘周期。
他開始構建優化版數學庫。
標準庫的浮點乘法子程序需要147個時鐘周期。
他的目標是：89個。
方法很簡單—至少原理上很簡單。標準庫為了兼容所有數據類型和邊界情況，加入了大量判斷分支。而他只需要針對團體賽可能的計算場景，裁剪掉不需要的通用性，用最直接的寄存器操作完成運算。
但這需要精確到每一個微碼步驟的調度。
如果調度錯一個周期，乘法的部分積就會錯位。如果寄存器衝突沒處理好，流水線就會空轉。
他需要同時考慮：
指令發射順序寄存器依賴關係內存訪問延遲微碼跳轉的預判懲罰這些變量互相耦合，構成一個極其複雜的優化問題。
但對於他而言—
這只是一道有趣的題。
七點十五分，林楓醒了。
他看到陸沉坐在床邊，雙眼微閉，以為他在打坐。
「修仙呢？」林楓揉著眼睛坐起來。
陸沉睜開眼。
「寫完了。」
「啊？」
「數學庫。」陸沉說，「乘除法、浮點運算、矩陣基本操作，大概四十幾個函數，比賽的時候直接用就行。」
林楓沉默了五秒鐘。
「————你一早上寫的？」
「嗯。」
「在腦子裡？」
陸沉想了想，覺得解釋起來太複雜，於是只說：「差不多。
林楓張了張嘴，最終什麼也沒說，默默起床洗漱去了。
八點整，中國隊集合完畢，前往計算中心。
團體賽的算法設計模塊在主賽場進行。
十二支代表隊各占據一片區域，每隊一台BESM—6終端，配發題目和參考手冊。
陸沉注意到，蘇聯隊坐最前排，東德隊和波蘭隊分列兩側。
中國隊的位置在第三排左側，旁邊是匈牙利隊。
落座時，一個戴眼鏡的匈牙利男生朝他們點了點頭，用口音濃重的英語說：「祝好運」
。
陸沉點頭回禮。
八點三十分，主考官走到講台前。
那是位五十多歲的蘇聯教授，灰白的頭髮梳得一絲不苟，他用俄語宣讀比賽規則，旁邊有翻譯用英語複述。
「本次算法設計模塊的題目，由蘇聯科學院計算中心提供。」
「限時四小時。」
「評分標準：正確性占50%，運行效率占40%，代碼結構占10%。」
「可以使用任何程式語言，但評測將在BESM—6實機上運行。」
「現在，分發題目。」
題目是密封在牛皮紙袋裡的。陸沉拆開，抽出裡面的紙張。
只有一頁紙。
上面是一段簡短的描述，和一組數學公式。
陸沉的目光掃過題目。
然後，他的瞳孔微微收縮了一下。
不是因為難。
是因為他見過這道題。
準確地說，是前世見過。
這道題的核心，是求解大規模稀疏線性方程組的預條件共軛梯度法—一種在計算數學中極其重要的疊代算法。
預條件技術還處於萌芽階段。
共軛梯度法雖然在五十年代就被提出，但因為數值穩定性和收斂速度的問題，一直沒能在實際工程中廣泛使用。
直到七十年代末，預條件技術的突破才讓這個方法真正實用化。
而這道題，恰恰要求選手設計一個預條件子，並實現完整的求解流程。
陸沉放下題目。
他知道這道題的標準解法一不完整的Cholesky分解作為預條件子，結合共軛梯度疊代。這是他前世做數值計算時爛熟於心的東西。
但問題在於——
1988年，不完整的Cholesky分解的論文還沒有發表。
原始論文是1990年才出現的。
如果他直接拿出這個解法，會引起什麼反應？
不過這個念頭只停留了一瞬。
他是來比賽的。
至於之後的事情，之後再說。
陸沉坐到終端前，開始敲擊鍵盤。
中國隊的分工是：陸沉負責核心算法設計，林楓負責輸入輸出和測試用例，另外兩名隊員負責文檔和輔助驗證。
但開賽十五分鐘後，林楓就發現了一個問題。
「陸沉。」他壓低聲音，「你寫的這個預條件子————是什麼方法？」
「不完整的Cholesky分解。」
林楓翻了翻參考手冊：「手冊上沒有。」
「嗯。
」
「那你怎麼————」
「推導出來的。」陸沉沒有停下手上的動作，「共軛梯度法的收斂速度取決於係數矩陣的條件數。如果能找到一個近似分解，使得預條件後的矩陣特徵值聚集，就能加速收斂。不完整分解的核心思想是，只保留原始矩陣稀疏結構內的元素，其他位置直接置零。」
林楓沉默了。
這些話他每一個字都聽得懂，但連在一起就變成了一堵牆。
他決定不再問，專心做自己能做的事。
一個小時後，陸沉完成了核心代碼。
他靠在椅背上，閉上眼睛，讓代碼在腦中的BESM—6模擬器上跑了一遍。
正確。
效率標準解法的約60%運行時間。
夠用了。
他重新睜開眼睛，準備繼續完善文檔。
就在這時，他注意到賽場前方出現了一陣輕微的騷動。
蘇聯隊的區域裡，幾個隊員正在低聲爭論什麼。
主考官走過去，聽了一會兒，然後點了點頭，對全場說：「蘇聯隊請求更換終端。原終端出現故障。」
工作人員開始檢查設備，陸沉的目光落在蘇聯隊隊長的臉上——那是一個十七八歲的金髮少年，眉頭緊鎖，神情有些焦躁。
不是因為設備故障。
設備故障是藉口。
真正的原因是：他們被題目卡住了。
預條件共軛梯度法這道題，如果沒有不完整分解的思路，就只能用最簡單的對角預條件雅可比預條件。
但雅可比預條件對這道題的病態矩陣效果很差，收斂極慢，甚至可能不收斂。
蘇聯隊大概試了雅可比，發現跑不通，以為是機器出了問題。
陸沉收回目光，繼續寫文檔。
這是比賽。
賽場上，沒有義務提醒對手。
十一點四十分，距離比賽結束還有五十分鐘。
陸沉完成了全部代碼和文檔。林楓的測試用例也準備好了。
「提交嗎？」林楓問。
「等一下。」陸沉說，「我再優化一個地方。」
他重新打開代碼文件，定位到預條件子的構造部分。
其實現在提交，成績已經足夠好了。
不完整的Cholesky分解比雅可比預條件快至少一個數量級，中國隊在這個模塊上的優勢是碾壓級的。
但陸沉忽然想試試另一個思路。
如果不完整的Cholesky分解是1980年的解法，那麼—
他能不能把時間線再往前推一點？
比如，1990年代才成熟的多重網格預條件？
不。時間不夠。四十分鐘寫不完一個完整的多重網格框架。
但有一個折中的思路。
他可以在不完整分解的基礎上，加入一個簡單的塊對角預處理，針對這道題矩陣的特殊分塊結構。
這個改進不大，但能進一步壓縮15%的運行時間。
而且，可以在現有代碼的基礎上用十分鐘改完。
他動手了。
十一點五十五分。
陸沉按下保存鍵。
「提交。」
林楓長長地呼出一口氣，像是終於卸下了什麼重擔。
評測過程是公開的。
各隊的程序被依次送入BESM—6主機，在統一的測試集上運行，運行時間和結果實時顯示在賽場前方的大屏幕上。
第一隊，保加利亞。運行結果：部分正確。運行時間：47.3秒。
第二隊，捷克斯洛伐克。運行結果：正確。運行時間：42.1秒。
第三隊，東德。運行結果：正確。運行時間：38.7秒。
隨著結果一個個公布，賽場裡的氣氛漸漸緊張起來。正確完成這道題的隊伍並不多，大多數要麼結果錯誤，要麼運行超時。
第六隊，匈牙利。運行結果：正確。運行時間：35.2秒。
匈牙利隊的區域裡發出一陣壓低聲音的歡呼。戴眼鏡的男生朝陸沉這邊看了一眼，比了個大拇指。
第七隊，蘇聯。運行結果：正確。運行時間：
屏幕上跳動了一下。
31.4秒。
蘇聯隊的區域裡，隊員們終於露出了笑容。金髮隊長靠在椅背上，神色明顯放鬆下來0
31.4秒。目前全場最快。
第八隊，波蘭。運行結果：正確。運行時間：33.8秒。
第九隊，羅馬尼亞。運行結果：部分正確。運行時間：超時。
第十隊，中國。
陸沉感覺到林楓的身體繃緊了。
屏幕上的數字開始跳動。
加載程序。
初始化數據。
開始計算。
計時器的數字飛速增長。
0.5秒。1.0秒。1.5秒。
林楓死死盯著屏幕。
陸沉倒是很平靜。
他已經知道了結果。
2.1秒。
計時停止。
運行結果：正確。
.
——
運行時間：2.1秒。
賽場安靜了一瞬。
然後「什麼？」
聲音是從蘇聯隊的區域傳出來的。
金髮隊長站了起來，盯著屏幕上的數字，臉上的表情從困惑變成難以置信。
2.1秒。
比第二名快了將近十五倍。
這不是「更快」。
這是不在同一個維度。
主考官也愣住了。他低頭檢查評測系統的日誌，確認沒有出錯。
沒有出錯。
日誌顯示，中國隊的程序確實在2.1秒內完成了全部計算任務。
而且，內存占用只有標準解法的三分之一。
主考官抬起頭，看向中國隊的方向。
「你們————」他用俄語說，然後切換成英語，「你們的預條件子，用的是什麼方法？
」
翻譯還沒開口，陸沉已經用俄語回答了。
「不完整的Cholesky分解，結合塊對角預處理。」
主考官的眼神變了。
「不完整的Cholesky分解？」他重複了一遍，「你是指————對係數矩陣做不完全的三角分解，捨棄填充元？」
「是的。」
「這個方法的收斂性」」
「有保證。」陸沉說，「對於M矩陣，不完整分解的存在性和穩定性都可以證明。具體來說，如果係數矩陣是M矩陣，則任意捨棄填充元的不完整Cholesky分解都存在，且預條件後的矩陣特徵值均為正實數。這道題的矩陣正好滿足M矩陣條件。」
主考官沉默了好一會兒。
「你————證明過嗎？」
「推導過。」陸沉說，「證明過程在我的文檔附錄里。」
主考官快步走向評測終端，調出中國隊提交的文檔。
屏幕上的內容一頁頁翻過。
算法描述。複雜度分析。數值實驗。
然後，他看到了附錄。
那裡有一段簡潔而嚴謹的證明，從M矩陣的定義出發，逐步推導出不完整Cholesky分解的存在性和穩定性條件。
推導過程乾淨得像一場外科手術。
主考官看了很久。
然後他轉過身，用一種很奇怪的語氣說：「中國隊。算法設計模塊。滿分。」
他頓了頓，又補充了一句：「附加分。10分。」
附加分。
這是本屆比賽第一次出現附加分。
林楓猛地轉過頭看陸沉，眼睛瞪得像銅鈴。
陸沉只是平靜地收拾著桌上的紙筆。
但他的手指，微微收緊了。
不是因為緊張。
是因為他知道，這件事不會就這麼結束。
一個十歲的中國孩子，在莫斯科的賽場上，拿出了一套比世界最前沿還要超前的數值算法。
這不是數學競賽。
這是某種信號。
他抬頭看了一眼賽場後方的觀察席。
那裡坐著幾個沒有佩戴參賽證件的人。
其中一個，是索科洛夫。
索科洛夫正低頭在筆記本上寫著什麼，似乎感覺到陸沉的目光，抬起頭來。
隔著整個賽場的距離，兩人再次對視。
索科洛夫合上了筆記本。
他的表情，看不出任何情緒。
但他的眼神，像是在看一件他找了很久的東西。
莫斯科的清晨來得早。
六點半，天已經大亮。
陸沉睜開眼，腦海中的倒計時剛好歸零四個小時的睡眠，足夠恢復精力了。
林楓還在睡，呼吸均勻。
昨晚他在終端前待到十一點，反覆熟悉BESM—6的指令集，最後是被值班老師趕回來的。
陸沉沒有叫醒他。他安靜地洗漱，然後坐在床邊，閉上眼睛。
意識沉入那片他稱之為「構建空間」的領域。
這是他的超算大腦真正施展威力的地方。
在他的感知中，BESM—6的硬體結構像一張三維藍圖般展開。
寄存器組、內存分頁、指令預取隊列、微碼存儲器—每一個模塊都清晰可見，每一個信號傳遞的時序都精確到時鐘周期。
他開始構建優化版數學庫。
標準庫的浮點乘法子程序需要147個時鐘周期。
他的目標是：89個。
方法很簡單—至少原理上很簡單。標準庫為了兼容所有數據類型和邊界情況，加入了大量判斷分支。而他只需要針對團體賽可能的計算場景，裁剪掉不需要的通用性，用最直接的寄存器操作完成運算。
但這需要精確到每一個微碼步驟的調度。
如果調度錯一個周期，乘法的部分積就會錯位。如果寄存器衝突沒處理好，流水線就會空轉。
他需要同時考慮：
指令發射順序寄存器依賴關係內存訪問延遲微碼跳轉的預判懲罰這些變量互相耦合，構成一個極其複雜的優化問題。
但對於他而言—
這只是一道有趣的題。
七點十五分，林楓醒了。
他看到陸沉坐在床邊，雙眼微閉，以為他在打坐。
「修仙呢？」林楓揉著眼睛坐起來。
陸沉睜開眼。
「寫完了。」
「啊？」
「數學庫。」陸沉說，「乘除法、浮點運算、矩陣基本操作，大概四十幾個函數，比賽的時候直接用就行。」
林楓沉默了五秒鐘。
「————你一早上寫的？」
「嗯。」
「在腦子裡？」
陸沉想了想，覺得解釋起來太複雜，於是只說：「差不多。
林楓張了張嘴，最終什麼也沒說，默默起床洗漱去了。
八點整，中國隊集合完畢，前往計算中心。
團體賽的算法設計模塊在主賽場進行。
十二支代表隊各占據一片區域，每隊一台BESM—6終端，配發題目和參考手冊。
陸沉注意到，蘇聯隊坐最前排，東德隊和波蘭隊分列兩側。
中國隊的位置在第三排左側，旁邊是匈牙利隊。
落座時，一個戴眼鏡的匈牙利男生朝他們點了點頭，用口音濃重的英語說：「祝好運」
。
陸沉點頭回禮。
八點三十分，主考官走到講台前。
那是位五十多歲的蘇聯教授，灰白的頭髮梳得一絲不苟，他用俄語宣讀比賽規則，旁邊有翻譯用英語複述。
「本次算法設計模塊的題目，由蘇聯科學院計算中心提供。」
「限時四小時。」
「評分標準：正確性占50%，運行效率占40%，代碼結構占10%。」
「可以使用任何程式語言，但評測將在BESM—6實機上運行。」
「現在，分發題目。」
題目是密封在牛皮紙袋裡的。陸沉拆開，抽出裡面的紙張。
只有一頁紙。
上面是一段簡短的描述，和一組數學公式。
陸沉的目光掃過題目。
然後，他的瞳孔微微收縮了一下。
不是因為難。
是因為他見過這道題。
準確地說，是前世見過。
這道題的核心，是求解大規模稀疏線性方程組的預條件共軛梯度法—一種在計算數學中極其重要的疊代算法。
預條件技術還處於萌芽階段。
共軛梯度法雖然在五十年代就被提出，但因為數值穩定性和收斂速度的問題，一直沒能在實際工程中廣泛使用。
直到七十年代末，預條件技術的突破才讓這個方法真正實用化。
而這道題，恰恰要求選手設計一個預條件子，並實現完整的求解流程。
陸沉放下題目。
他知道這道題的標準解法一不完整的Cholesky分解作為預條件子，結合共軛梯度疊代。這是他前世做數值計算時爛熟於心的東西。
但問題在於——
1988年，不完整的Cholesky分解的論文還沒有發表。
原始論文是1990年才出現的。
如果他直接拿出這個解法，會引起什麼反應？
不過這個念頭只停留了一瞬。
他是來比賽的。
至於之後的事情，之後再說。
陸沉坐到終端前，開始敲擊鍵盤。
中國隊的分工是：陸沉負責核心算法設計，林楓負責輸入輸出和測試用例，另外兩名隊員負責文檔和輔助驗證。
但開賽十五分鐘後，林楓就發現了一個問題。
「陸沉。」他壓低聲音，「你寫的這個預條件子————是什麼方法？」
「不完整的Cholesky分解。」
林楓翻了翻參考手冊：「手冊上沒有。」
「嗯。
」
「那你怎麼————」
「推導出來的。」陸沉沒有停下手上的動作，「共軛梯度法的收斂速度取決於係數矩陣的條件數。如果能找到一個近似分解，使得預條件後的矩陣特徵值聚集，就能加速收斂。不完整分解的核心思想是，只保留原始矩陣稀疏結構內的元素，其他位置直接置零。」
林楓沉默了。
這些話他每一個字都聽得懂，但連在一起就變成了一堵牆。
他決定不再問，專心做自己能做的事。
一個小時後，陸沉完成了核心代碼。
他靠在椅背上，閉上眼睛，讓代碼在腦中的BESM—6模擬器上跑了一遍。
正確。
效率標準解法的約60%運行時間。
夠用了。
他重新睜開眼睛，準備繼續完善文檔。
就在這時，他注意到賽場前方出現了一陣輕微的騷動。
蘇聯隊的區域裡，幾個隊員正在低聲爭論什麼。
主考官走過去，聽了一會兒，然後點了點頭，對全場說：「蘇聯隊請求更換終端。原終端出現故障。」
工作人員開始檢查設備，陸沉的目光落在蘇聯隊隊長的臉上——那是一個十七八歲的金髮少年，眉頭緊鎖，神情有些焦躁。
不是因為設備故障。
設備故障是藉口。
真正的原因是：他們被題目卡住了。
預條件共軛梯度法這道題，如果沒有不完整分解的思路，就只能用最簡單的對角預條件雅可比預條件。
但雅可比預條件對這道題的病態矩陣效果很差，收斂極慢，甚至可能不收斂。
蘇聯隊大概試了雅可比，發現跑不通，以為是機器出了問題。
陸沉收回目光，繼續寫文檔。
這是比賽。
賽場上，沒有義務提醒對手。
十一點四十分，距離比賽結束還有五十分鐘。
陸沉完成了全部代碼和文檔。林楓的測試用例也準備好了。
「提交嗎？」林楓問。
「等一下。」陸沉說，「我再優化一個地方。」
他重新打開代碼文件，定位到預條件子的構造部分。
其實現在提交，成績已經足夠好了。
不完整的Cholesky分解比雅可比預條件快至少一個數量級，中國隊在這個模塊上的優勢是碾壓級的。
但陸沉忽然想試試另一個思路。
如果不完整的Cholesky分解是1980年的解法，那麼—
他能不能把時間線再往前推一點？
比如，1990年代才成熟的多重網格預條件？
不。時間不夠。四十分鐘寫不完一個完整的多重網格框架。
但有一個折中的思路。
他可以在不完整分解的基礎上，加入一個簡單的塊對角預處理，針對這道題矩陣的特殊分塊結構。
這個改進不大，但能進一步壓縮15%的運行時間。
而且，可以在現有代碼的基礎上用十分鐘改完。
他動手了。
十一點五十五分。
陸沉按下保存鍵。
「提交。」
林楓長長地呼出一口氣，像是終於卸下了什麼重擔。
評測過程是公開的。
各隊的程序被依次送入BESM—6主機，在統一的測試集上運行，運行時間和結果實時顯示在賽場前方的大屏幕上。
第一隊，保加利亞。運行結果：部分正確。運行時間：47.3秒。
第二隊，捷克斯洛伐克。運行結果：正確。運行時間：42.1秒。
第三隊，東德。運行結果：正確。運行時間：38.7秒。
隨著結果一個個公布，賽場裡的氣氛漸漸緊張起來。正確完成這道題的隊伍並不多，大多數要麼結果錯誤，要麼運行超時。
第六隊，匈牙利。運行結果：正確。運行時間：35.2秒。
匈牙利隊的區域裡發出一陣壓低聲音的歡呼。戴眼鏡的男生朝陸沉這邊看了一眼，比了個大拇指。
第七隊，蘇聯。運行結果：正確。運行時間：
屏幕上跳動了一下。
31.4秒。
蘇聯隊的區域裡，隊員們終於露出了笑容。金髮隊長靠在椅背上，神色明顯放鬆下來0
31.4秒。目前全場最快。
第八隊，波蘭。運行結果：正確。運行時間：33.8秒。
第九隊，羅馬尼亞。運行結果：部分正確。運行時間：超時。
第十隊，中國。
陸沉感覺到林楓的身體繃緊了。
屏幕上的數字開始跳動。
加載程序。
初始化數據。
開始計算。
計時器的數字飛速增長。
0.5秒。1.0秒。1.5秒。
林楓死死盯著屏幕。
陸沉倒是很平靜。
他已經知道了結果。
2.1秒。
計時停止。
運行結果：正確。
.
——
運行時間：2.1秒。
賽場安靜了一瞬。
然後「什麼？」
聲音是從蘇聯隊的區域傳出來的。
金髮隊長站了起來，盯著屏幕上的數字，臉上的表情從困惑變成難以置信。
2.1秒。
比第二名快了將近十五倍。
這不是「更快」。
這是不在同一個維度。
主考官也愣住了。他低頭檢查評測系統的日誌，確認沒有出錯。
沒有出錯。
日誌顯示，中國隊的程序確實在2.1秒內完成了全部計算任務。
而且，內存占用只有標準解法的三分之一。
主考官抬起頭，看向中國隊的方向。
「你們————」他用俄語說，然後切換成英語，「你們的預條件子，用的是什麼方法？
」
翻譯還沒開口，陸沉已經用俄語回答了。
「不完整的Cholesky分解，結合塊對角預處理。」
主考官的眼神變了。
「不完整的Cholesky分解？」他重複了一遍，「你是指————對係數矩陣做不完全的三角分解，捨棄填充元？」
「是的。」
「這個方法的收斂性」」
「有保證。」陸沉說，「對於M矩陣，不完整分解的存在性和穩定性都可以證明。具體來說，如果係數矩陣是M矩陣，則任意捨棄填充元的不完整Cholesky分解都存在，且預條件後的矩陣特徵值均為正實數。這道題的矩陣正好滿足M矩陣條件。」
主考官沉默了好一會兒。
「你————證明過嗎？」
「推導過。」陸沉說，「證明過程在我的文檔附錄里。」
主考官快步走向評測終端，調出中國隊提交的文檔。
屏幕上的內容一頁頁翻過。
算法描述。複雜度分析。數值實驗。
然後，他看到了附錄。
那裡有一段簡潔而嚴謹的證明，從M矩陣的定義出發，逐步推導出不完整Cholesky分解的存在性和穩定性條件。
推導過程乾淨得像一場外科手術。
主考官看了很久。
然後他轉過身，用一種很奇怪的語氣說：「中國隊。算法設計模塊。滿分。」
他頓了頓，又補充了一句：「附加分。10分。」
附加分。
這是本屆比賽第一次出現附加分。
林楓猛地轉過頭看陸沉，眼睛瞪得像銅鈴。
陸沉只是平靜地收拾著桌上的紙筆。
但他的手指，微微收緊了。
不是因為緊張。
是因為他知道，這件事不會就這麼結束。
一個十歲的中國孩子，在莫斯科的賽場上，拿出了一套比世界最前沿還要超前的數值算法。
這不是數學競賽。
這是某種信號。
他抬頭看了一眼賽場後方的觀察席。
那裡坐著幾個沒有佩戴參賽證件的人。
其中一個，是索科洛夫。
索科洛夫正低頭在筆記本上寫著什麼，似乎感覺到陸沉的目光，抬起頭來。
隔著整個賽場的距離，兩人再次對視。
索科洛夫合上了筆記本。
他的表情，看不出任何情緒。
但他的眼神，像是在看一件他找了很久的東西。