科學計算：科技創新的第三種方法*

文/陳志明

中國科學院數學與系統科學研究院 北京 100190

1 計算數學和科學計算的興起和發展

1947年Von Neumann和Goldstine在《美國數學會通報》發表了題為“高階矩陣的數值求逆”的著名論文，開啟了現代計算數學的研究。計算數學研究為可在計算機上運行的數值算法的構造及其數學理論，包括算法的收斂性、精確性、穩定性和計算復雜性等。60多年來，伴隨著計算機技術的進步，計算數學得到了蓬勃發展，逐漸成為一個獨立和重要的學科。

上個世紀90年代，由于微電子技術的發展和應用方面需求的推動，計算機得到了飛速發展，計算數學、應用數學、計算機科學以及應用領域結合在一起產生了科學計算這一新的交叉學科。科學計算利用先進的計算能力認識和解決復雜的科學工程問題，它融建模、算法、軟件研制和計算模擬為一體，是計算機實現其在高科技領域應用的必不可少的紐帶和工具。計算、理論和實驗一起已成為當今世界科學技術創新的主要方式。

進入21世紀以來，高性能計算機發展迅速，已經進入了千萬億次時代。千萬億次科學計算應用將顯著提升人類在氣候與生態環境、航空航天、生命科學、材料科學、國家安全等領域中的科技創新能力，產生重大科學理論和應用突破。當前，基于通用CPU和GPU異構的千萬億次計算機的總處理器核數已超過10萬。不斷膨脹的并行規模給并行算法研究及應用程序研制不斷提出新的挑戰。研制適應于千萬億次科學計算的高性能應用軟件成為我國及世界科技發展所面臨的一個重大問題。

高性能科學計算由于其在國家安全和科技創新方面的重要作用日益受到世界各國的重視。以美國為例，自1996年實施加速戰略計算計劃（ASCI計劃）以來，在國防、氣候與環境、能源、航空航天、工業仿真優化、生物制藥等行業領域，針對流體力學、結構力學、材料科學、天體物理、等離子體物理、全球氣候變化、生物計算等學科，發展并行算法庫，研制并行應用程序，突破了高效使用數千至數萬核開展大規模并行計算的若干關鍵瓶頸，在某些方面甚至達到了10多萬核的并行規模，形成了一批有代表性的并行數值軟件包和并行應用程序，如ETSc、Hypre、SAMRAI等。

歐盟投入巨資建設歐洲“高性能計算生態系統”，2007年包括德國、英國、法國、意大利等14個歐洲國家的代表宣布將合作開展歐洲先進計算合作（PRACE）計劃，大力發展先進的計算方法、算法，研制大型實際應用軟件，以加速提高歐盟的高性能計算水平。日本通過成功研制峰值計算速度達40多萬億次的超級計算機“地球模擬器”大力推進高性能科學與工程計算的研究，在全球氣候變化數值模擬研究方面取得了突出的成果，目前日本正在推進耗資10億美元的萬萬億次計算機計劃，研究納米和生命科學。

我國非常重視計算數學和科學計算的發展，在歷次科學規劃中都將計算數學和科學計算列為重點發展領域。早在1956年制定的《十二年科學技術發展規劃》中，計算數學的發展和計算機在科學技術中的應用就已與計算機硬件的研制開發相并列。上個世紀90年代，科技部先后資助了兩期攀登計劃項目“大規模科學與工程計算的方法和理論”，1999年起將“大規模科學計算研究”、“高性能科學計算研究”和“適應于千萬億次科學計算的新型計算模式”作為國家重點基礎研究發展計劃（“973”計劃）項目予以連續支持，2011年國家自然科學基金委又啟動了“高性能科學計算的基礎算法和可計算建模”的重大研究計劃。

2 計算數學的主要研究內容和一些新進展

隨著高性能計算機技術的進步，計算機的計算能力和數據處理能力得到大幅度提升，當前科學工程計算所需要解決的問題越來越復雜、越來越細致、越來越接近實際問題的模型。這對充分發揮計算機巨大能力，解決實際問題的高效計算方法提出了越來越迫切的需求。下面從分數值代數、數值逼近、最優化方法和微分方程計算方法4個方面簡要介紹計算數學的主要研究內容和最新進展。

2.1 數值代數

數值代數主要研究代數方程組,代數特征值問題和最小二乘問題的數值求解方法，數值代數的算法在科學計算中具有基礎作用。偏微分方程離散產生的大型稀疏代數方程組快速算法一直是科學計算的重要研究課題，過去30年取得了很大進展，其標志性的例子是橢圓離散問題的多重網格方法，它從上世紀70年代后期的幾何多重網格方法開始，發展成通用的可擴展的代數多重網格方法AMG，以通用AMG程序為基礎，研究離散偏微分方程的可擴展算法成為一個非常重要的研究方向。另一個重要進展是稀疏代數方程組的直接法，目前對于二維偏微分方程離散的代數方程組，多界面方法及其程序MUMPS的計算復雜性已降為O（N1.5）,較好滿足了許多二維偏微分方程計算的實際需求，如何降低多界面方法對三維離散偏微分方程的計算復雜性成為重要的研究課題。

大型稀疏代數問題的快速算法的另一個基本問題是特征值問題的計算方法，上世紀90年代發展成熟的帶隱式重啟動的Arnoldi算法已經能夠求解大部分實際應用中出現的大規模線性特征值問題，但對于一些特殊應用中出現的特殊要求的特征值問題還不能有效求解。關于特征向量非線性的非線性特征值問題，尤其是對于電子結構計算中的非線性特征值問題，現有的算法從收斂性、收斂速度、計算指定的特征值等方面均不能滿足要求。

2.2 數值逼近

對數據、圖像、函數等對象的逼近是計算方法中最基本的手段之一。眾所周知，現代信息技術的基礎是數據的表示和變換方法，有效的數據表示和數學變換為計算機處理大規模信息提供了可能，隨著信息技術的高速發展和越來越復雜數據處理的需要，新問題不斷涌現，逼近論已成為計算方法中最為活躍的一個部分。數值逼近的一個重要領域是計算幾何，它是由函數逼近論、微分幾何學以及計算方法等學科交叉形成的學科,主要研究幾何形狀的構造、計算機表示、分析和綜合，是計算機輔助幾何設計的數學基礎。

逼近論的最新進展包括基函數、冗余框架或更一般的冗余詞典的稀疏逼近，其基本思想是利用一個非線性逼近格式得到函數、數據或圖像等對象的稀疏逼近。過去20多年小波理論及其應用的快速發展和最近壓縮感知的快速發展為非線性稀疏逼近提供了重要的理論基礎和計算方法，這些理論和方法與調和分析、小波理論、非線性逼近和優化方法等理論密切關聯，它們突破了經典理論方法的局限，極大地提高了復雜數據信息處理的能力，成為圖像科學、計算機圖形學、數據挖掘、機器學習理論的重要工具。

2.3 最優化方法

最優化問題廣泛見之于工程、國防、經濟、管理等許多重要領域，在結構設計、化學反應設計、電力分配、石油開采等方面都有直接的應用。最優化計算方法還和計算數學中的數值逼近、常微分方程中的變分原理、微分方程反演以及非線性代數方程組等分支和問題有交叉和應用。許多領域諸如壓縮感知、數據挖掘、核磁共振、最優控制、圖像處理、矩陣方程中的優化問題其規模往往很大，這對于最優化領域的計算方法的設計既是挑戰又是機遇。

偏微分方程約束優化問題與無窮維優化問題在航天飛行器設計、衛星紅外掃描儀、醫療設備形狀設計、刀片渦刀片執行器控制、水庫管理、天氣預報、大氣污染控制、石油勘探和開采等許多工業、醫學和經濟等領域中有著廣泛應用,是這些領域中最具有挑戰性的困難之一。這些優化問題的目標函數值和梯度值的計算往往需要求解極復雜的偏微分方程，與常見的優化問題相比，問題的規模常常很大，需要上千萬甚至上億自由度，有時目標函數是非光滑、非一致凸甚至是非凸的，往往需要求解一連串的優化問題及大規模非光滑全局優化問題，而且優化問題的魯棒解和有效解需要很好地融合問題的結構、數值模擬和優化算法3個方面。

2.4 微分方程計算方法

哈密爾頓系統辛幾何算法是由我國著名數學家馮康院士于上世紀80年代開始系統創立的，1997年獲得國家自然科學獎一等獎。無論在理論上還是在應用上，它的重要性均受到國際學術界的高度重視。特別是，它的長時間計算的優越性使得天體物理學、量子物理學、納米材料和分子生物學等眾多領域的科學家們進一步認識了科學計算這一研究方法的重要作用。哈密爾頓系統辛幾何算法的基本思想是“數值格式應該盡可能多的保持原系統的本質特征和內在對稱性”。根據這個思想，近年來國外學者先后建立了動力系統李群算法、無窮維哈密爾頓系統多辛幾何算法、基于微分形式的有限元方法和隨機動力系統的保結構算法等。現已形成了包括哈密爾頓系統辛幾何算法、切觸系統的切觸算法、保體積系統的保體積算法等在內的動力系統保結構算法的理論與應用體系。

偏微分方程描述許多構成實際物理過程的各個不同階段的物理模型，其計算方法包括如何針對不同偏微分方程的問題設計合適的網格和離散格式，如何設計可擴展的并行算法及其并行實現技術，在離散網格上給出方程的近似解。偏微分方程的高效計算方法研究在過去30年中取得了巨大的進步，突出表現在網格的自適應構造方法及理論研究的興起，非結構網格和混合網格上流體力學方程高精度高分辨率離散格式的進展。當前，在網格自適應方法的研究方面，主要有針對流體力學計算的結構網格自適應技術和針對橢圓拋物方程應用的基于后驗誤差估計的自適應有限元方法；在高精度高分辨率離散格式方面，流固耦合、多介質多相流問題的高效、皮實數值格式以及密切相關的網格構造的ALE方法，與ALE方法密切相關的網格自適應技術和移動網格技術、利用曲面造型技術產生的數據直接進行有限元結構分析的等幾何方法、充分利用所研究問題的結構的外微分有限元方法等得到越來越多的計算數學工作者的關注。

3 科學計算進一步發展的建議

3.1 大力發展大規模科學計算的基礎算法

科學計算能力包括計算機硬件設備和應用軟件及支撐軟件的算法的能力。2005年美國總統信息技術咨詢委員會報告指出：“盡管處理器性能的顯著增長廣為人知，然而改進算法和程序庫對于提高計算模擬能力的貢獻是如此之大，如同在硬件上的改進一樣。”以在科學計算應用中廣泛出現三維拉普拉斯方程計算求解為例，從上世紀50年代的高斯消去法到80年代的多重網格法，算法的改進使計算量從正比于網格數N的7/3次方下降到最優的計算量正比于N，對于N等于100萬，計算效率就改進1億倍！2009年出版的美國世界技術評估中心WTEC報告中對1998—2006年獲著名超級計算Gorden Bell獎的應用程序進行了評估，指出盡管獲獎程序的應用領域各不相同，但共同點是，算法（線性代數、圖剖分、區域分裂、高階離散）的進步使得獲Gorden Bell獎應用程序對計算能力提高的貢獻超過摩爾定律。

當前科學計算所要解決的數值模擬問題往往非常復雜，給數值方法研究帶來了巨大的挑戰。數值方法研究目前面臨的突出共同難點表現為：高維數、計算規模大、多時空尺度、強非線性、不適定、長時間、奇異性、幾何復雜、高度病態、精度要求高等，并非有了高性能計算機就可以解決這些難點。數值模擬的困難常常表現為規模大得難以承受或失去時效；算法不收斂或誤差積累使結果面目全非；花費大量計算機時卻得不到結果或只得到錯誤結果；由于問題的奇異性使計算非正常中止；問題太復雜使算法難以實現等。這些難點問題近年來受到廣泛關注，已成為科學計算的研究熱點。

3.2 大力發展高性能科學計算應用軟件平臺和框架

當前高性能計算機體系結構日趨復雜，CPU/GPU異構、數千計算結點、結點內多處理器、處理器內多核、核內多功能部件及多級存儲是其顯著特點，對應用軟件的研制提出了挑戰。當前，我國科學計算應用軟件的研制面臨兩大瓶頸：第一，計算效率低，應用程序通常只能發揮數百處理器核峰值性能的10%以下；第二，研制周期長，與高性能計算機的快速發展不匹配。不突破這兩個瓶頸，我國并行應用軟件的研制就很難在總體上跟上高性能計算機的發展速度，無法將計算機技術的進步有效地用于科技創新，無法在國家重大應用領域發揮其應有的價值。

為了突破“計算效率低”和“研制周期長”兩大瓶頸，近年來我國科學工作者根據并行應用程序的多層軟件體系結構，提出了“集成共性、支撐個性”的新型并行軟件研制方法，在此新思路下，研制成功三維并行結構自適應軟件框架JASMIN和三維并行自適應有限元軟件平臺PHG，這兩個平臺在基礎性共性算法（例如網格自適應和數百處理器核上的求解器）層次上對用戶屏蔽并行實現細節，并較好地解決了自適應并行實現中的負載平衡難題，在數10萬億次國產并行計算機上，實現了高效并行計算。

在框架和平臺的支撐下，各專業領域的科學計算研究人員可以集中于物理模型和計算方法的創新研究，無需了解并行計算的細節，就可以將新的物理模型和計算方法快速融入到大規模并行計算中，而計算機系統的研究人員，則可以集中于更高速度和更大規模計算機系統的研制，而無須顧及實現具體科學和工程計算的細節。

3.3 大力加強自主高性能計算科學軟件研制

高性能科學計算應用軟件的重要特點是多學科交叉，它是數學、物理、力學等基礎學科和相應應用學科及計算機軟件技術相結合而形成的以算法為核心，以計算機系統為支撐的知識密集型集成化信息產品，領域專業性非常強，只有建立高水平的多學科交叉研究隊伍，針對實際科學問題經過長時間的積累和沉淀，才能研制成功。

高水平的計算科學軟件需要先進的算法，我們建議在國家重大科技項目執行中能特別重視高性能計算科學軟件的自主研制，鼓勵更多的計算數學工作者深入科學計算中的瓶頸問題如材料計算、流體計算、電磁場計算、輻射流體力學計算、納米計算和生物計算中的算法研究、多尺度模型的分析與計算以及非平衡態的計算等，算法的創新要結合適合于計算的模型進行研究。

致謝 本文得到北京應用物理與計算數學研究所江松、莫則堯研究員，新加坡國立大學沈佐偉教授，中山大學許躍生教授，復旦大學蘇仰鋒教授，中科院數學與系統科學院白中治、戴彧虹、洪佳林、徐國良、張林波研究員和許志強副研究員的大力幫助，特此致謝。

1 2005年總統信息技術咨詢委員會報告.計算科學：確保美國競爭力.北京應用物理與計算數學研究所信息中心譯，2006年4月.

2 WTEC Panel Report.International assessment on research and development in simulation-based engineering and science.Washington:World Technology Evaluation Center,2009.http://wtec.org.

3 中國科學院數理學部“高性能計算戰略研究”咨詢組.加速發展我國高性能計算的若干建議.科研信息化技術與應用，2008,（3）.

4 Bader DA.面向千萬億次計算的算法與應用.都志輝等譯.北京：清華大學出版社，2008.

5 Grcar J F.John von neumann’s analysis of gaussian elimination and the origins of modern numerical analysis.SIAM Review,2011,53:607-682.

6 國家自然科學基金委.2011—2020年我國數學學科發展戰略研究，2010年.