科學計算：科技創(chuàng)新的第三種方法*

文/陳志明

中國科學院數(shù)學與系統(tǒng)科學研究院 北京 100190

1 計算數(shù)學和科學計算的興起和發(fā)展

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

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

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

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

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

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

2 計算數(shù)學的主要研究內(nèi)容和一些新進展

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

2.1 數(shù)值代數(shù)

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

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

2.2 數(shù)值逼近

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

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

2.3 最優(yōu)化方法

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

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

2.4 微分方程計算方法

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

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

3 科學計算進一步發(fā)展的建議

3.1 大力發(fā)展大規(guī)?？茖W計算的基礎(chǔ)算法

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

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

3.2 大力發(fā)展高性能科學計算應(yīng)用軟件平臺和框架

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

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

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

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

高性能科學計算應(yīng)用軟件的重要特點是多學科交叉，它是數(shù)學、物理、力學等基礎(chǔ)學科和相應(yīng)應(yīng)用學科及計算機軟件技術(shù)相結(jié)合而形成的以算法為核心，以計算機系統(tǒng)為支撐的知識密集型集成化信息產(chǎn)品，領(lǐng)域?qū)I(yè)性非常強，只有建立高水平的多學科交叉研究隊伍，針對實際科學問題經(jīng)過長時間的積累和沉淀，才能研制成功。

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

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

1 2005年總統(tǒng)信息技術(shù)咨詢委員會報告.計算科學：確保美國競爭力.北京應(yīng)用物理與計算數(shù)學研究所信息中心譯，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 中國科學院數(shù)理學部“高性能計算戰(zhàn)略研究”咨詢組.加速發(fā)展我國高性能計算的若干建議.科研信息化技術(shù)與應(yīng)用，2008,（3）.

4 Bader DA.面向千萬億次計算的算法與應(yīng)用.都志輝等譯.北京：清華大學出版社，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年我國數(shù)學學科發(fā)展戰(zhàn)略研究，2010年.