淺談數(shù)值計算方法的過去和未來

1、2024/2/29,淺談計算數(shù)學的過去和未來,趙金熙 南京大學計算機科學與技術(shù)系,2024/2/29,1.引言,Numerical analysis is the study of algorithms for the problems of continuous mathematics ----Lloyd N. Trefethen,1,“計算數(shù)學”就是研究在計算機上解決數(shù)學問題的理論和

2、數(shù)值方法。,今天的數(shù)值計算方法，無論從形式到內(nèi)容，還是從工具到效果，已遠非半世紀前Von Neumann、Lax等先驅(qū)們所處的環(huán)境和條件了，計算機技術(shù)和應用軟件的發(fā)展，讓計算數(shù)學展開了雙翼。許多迅速發(fā)展的其他學科和社會進步給計算數(shù)學的發(fā)展開拓出 更為廣闊的新天地。,Maxims About Numerical Mathematics and Computers ----L.N. Trefethen,There are th

3、ree great branches of science: theory, experiment, and computation. The fundamental law of computer science: As machines become more powerful, the efficiency of algorithms grows more important, not less.,

4、這里主要談二個方面：從計算物理的發(fā)展過程來看計算數(shù)學的過去；計算數(shù)學的未來50年.[1--3].,一. 計算數(shù)學發(fā)展的歷史回顧,,2,1. 從計算物理談起,計算數(shù)學的發(fā)展與科學工程計算是緊密相聯(lián)的，計算數(shù)學的發(fā)展歷史也就是與其他學科結(jié)合，利用計算機不斷形成新的理論及數(shù)值方法并不斷形成新的學科的歷史，例如：“計算物理”。,１９５９年５月美國總統(tǒng)發(fā)布命令，可以揭開曼哈頓計劃的內(nèi)幕，部分內(nèi)容可以解密。故以“計算物理方法”叢書的名義陸續(xù)編輯出版

5、,,我們常說:,計算物理的物質(zhì)基礎是計算機；計算物理的關(guān)鍵技術(shù)是“計算方法”和“程序設計”; 計算物理發(fā)展的原始動力是美國核武器研制的刺激。,三位計算機設計大師的貢獻,,H. Aiken (1900-1973)，,哈佛大學的博士研究生畢業(yè)。因做博士論文涉及到空間電荷傳導問題的計算，1937年提出方案，1939年得到IBM資助，1944年建成投入使用。這是繼電式計算機－Mark I,J. W. Manchly (1907-1980)，

6、,賓夕法尼亞物理博士，因從事天氣預報需要想設計計算機，1942年提出計算機方案，1945年底竣工，這就是世界上第一臺電子計算機－ENIAC機,J. Von Neumann (1903-1956),普林斯頓高級研究所，1945年在普林斯頓研制成MANIAC機，有力地支持美國氫彈研制，稱為計算機之父。（與中國的109丙機、J-501機相當）。,美國從1942年8月13日開始曼哈頓計劃，到1945年制造出三顆原子彈：代號為：“三一”，用于試驗

7、（7月16日），“瘦子”投于廣島(8月6日)，“胖子”投于長崎(8月9日)。歷時三年，涉及到理論物理、爆轟物理、中子物理、金屬物理、彈體彈道等大量的數(shù)值計算。,,1949年8月蘇聯(lián)第一次原子彈爆炸后，杜魯門總統(tǒng)在1950年1月31日下令繼續(xù)研究各種類型的原子彈武器，成立以氫彈之父特勒(E. Teller)為首的氫彈研制小組。直到1952年10月31日爆炸了代號為“麥克”的核試驗。,,在研制原子彈和氫彈過程中，許多物理規(guī)律必須通過計算

8、機上的計算摸清楚。計算物理、理論物理與實驗物理相輔相成相互促進共同發(fā)展，形成現(xiàn)代物理學的三大分支。,,由于核武器研制需要，1950年全球只有15臺，到了1962年9月僅美國就有16187臺計算機。,,60年代中期，由于硅平面工藝的出現(xiàn)，集成電路成為獨立的工藝，并且可借助計算機本身的力量而精益求精。硅的集成度平均三年增加4倍，而計算機本身每三年更新一次。,,60年代中期開始推出小型計算機，70年代末推出個人計算機，80年代中期

9、又推出高性能的超級微機。而計算物理發(fā)展所涉及的大規(guī)模科學計算和模擬所需要的大型計算機卻得到發(fā)展。,,1981年以哈佛大學普雷斯(W. H. Press)為首的11位著名科學家聯(lián)名上書，向美國國家科學基金會(NSF)呈送“發(fā)展計算物理的建議書”，大聲疾呼計算物理發(fā)展正處于一個危機階段，是NSF采取實質(zhì)性行動的時候了。,,1981年，戈爾在美國科學與電視藝術(shù)研究的一次演講中，首先提出“信息高速公路”這個很前瞻性的概念，可能受其父親以前曾向國

10、會提出“洲際高速公路”提案的影響。,,２.科學計算,,1983年一個由美國著名數(shù)學家拉克斯(P. Lax)為首的不同學科的專家委員會向美國政府提出的報告之中，強調(diào)“科學計算是關(guān)系到國家安全、經(jīng)濟發(fā)展和科技進步的關(guān)鍵性環(huán)節(jié)，是事關(guān)國家命脈的大事。”,,1984年美國政府大幅度地增加對科學計算經(jīng)費的支持, 新建成五個國家級超級計算中心（分別在普林斯頓大學、圣地亞哥、伊里諾大學、康奈爾大學、匹茲堡），配備當時最高性能的計算機，建立NSF-ne

11、t新網(wǎng)絡。,,80年代中期我國將“大規(guī)?？茖W與工程計算”列入國家資助重大項目。,,1987年起美國NSF把“科學與工程計算”、“生物工程”“全局性科學”作為三大優(yōu)先資助的領域。,,1990年美國國家研究委員會發(fā)表《振興美國數(shù)學：90年代的計劃》的報告，建議對由計算引發(fā)的數(shù)學給予特殊的鼓勵和資助。,,報告指出由于大存儲的高速計算機的使用已導致了科學和技術(shù)方面的兩大突出進展：,,一是大量用于設計工作的實驗被數(shù)學模型的研究逐步取代

12、，如航天飛機設計、反應堆設計、人工心瓣膜設計等；二是能獲取和存儲大量的數(shù)據(jù)，并能提取隱秘的信息，如計算機層析X射線攝影，核磁共振等。,,1991年以美國總統(tǒng)倡議的形式提出了“高性能計算與通信（HPCC）計劃”。這是為了保持和提高美國在計算和網(wǎng)絡的所有先進領域中的領導地位而制定的。,,該計劃為期五年（1992－1996），由美國8個重要部門負責實施。投資的重點（43％）是發(fā)展先進的軟件技術(shù)與并行算法，關(guān)鍵技術(shù)是可擴展的大規(guī)模并行計算。,

13、,要求到1996年高性能計算能力提高14倍，達到每秒萬億次浮點運算速度（1012 Teraops/S）。計算機網(wǎng)絡通迅能力提高1百倍，達到每秒109位（Gigabits/S）。,,該計劃中列舉的“挑戰(zhàn)”項目有：磁記錄技術(shù)、藥物設計、催化、燃燒、海洋模擬、臭氧洞、空氣污染、高速民用運輸機、數(shù)字解剖、蛋白質(zhì)結(jié)構(gòu)設計、金星成像等。,,1993年初美國總統(tǒng)發(fā)布“發(fā)展信息高速公路”（NII）的總統(tǒng)令。1994年4月美國總統(tǒng)發(fā)布“建立國家（地球）

14、空間數(shù)據(jù)基礎實施”（NSDI）的總統(tǒng)令。,,3．戰(zhàn)略計算,“戰(zhàn)略計算”一詞首次出現(xiàn)在1995年美國為了確保核庫存的性能、安全性、可靠性和更新需要而實施的“加速戰(zhàn)略計算創(chuàng)新（ASCI）計劃”。,這是因為美國克林頓總統(tǒng)在1995年8月11日宣布：“美國決定謀求真正的“零當量”全面禁止試驗核武器條約”。,,這并不意味著核競賽的結(jié)束，恰恰相反是核武器計劃新時代的開始，要求通過逼真的建模和模擬計算來取代傳統(tǒng)的反復試驗的工程處理方法。,,這主要依

15、賴于先進的數(shù)值計算和模擬能力，為此應用程序必須達到高分辯、三維、全物理和全系統(tǒng)的水平。,,為了確保ASCI目標的實現(xiàn)，采取一項相互關(guān)聯(lián)的策略措施：① 建立協(xié)調(diào)一致的管理，在三個防務計劃實驗室的基礎上組成“戰(zhàn)略計算和模擬辦公室”，統(tǒng)一指揮，由負責國家防務的副部長領導。,,② 致力于開發(fā)高級應用軟件。③ 致力于發(fā)展高性能計算。④ 建立解決問題的環(huán)境。⑤ 促進戰(zhàn)略聯(lián)合和協(xié)作。,,1995年8月22日（即美國總統(tǒng)宣布決定后的11天），能

16、源部（DOE）就采購世界上最快的一臺計算機（運算速度超過萬億次）交付圣地亞實驗室（96年12月安裝）。,,1996年2月20日，能源部公開招標，將購買兩臺每秒運算速度達3萬億次的計算機。并競爭下一代系統(tǒng)，2000年達10萬億次。本計劃實現(xiàn)的最后日期為2003或2004年，達到100萬億次（我國2000年8月宣布達3000億次）。,,1997財政年度美國總統(tǒng)提出1.216億美元作為實施五個策略的經(jīng)費預算。ASCI的學術(shù)戰(zhàn)略合作計劃（AS

17、AP）在1997年8月通過招標和簽訂合同方式，建立了五家合作中心：,,斯坦福大學的湍流綜合模擬中心；加州理工學院的模擬材料動態(tài)特性的計算中心；芝加哥大學的天體物理學熱核反應瞬間閃光研究中心；猶他大學的意外火災與爆炸模擬中心；伊利諾斯州州立大學的助推火箭模擬中心。,,1998年1月31日，美國副總統(tǒng)戈爾（Al. Gore）在美國加利福尼亞科學中心發(fā)表了題為“數(shù)字地球－二十一世紀認識地球的方式”的演講，首次提出“數(shù)字地球”的全新概念。,,為

18、此需要的技術(shù)有：計算科學、海量儲存、衛(wèi)星圖像、寬帶網(wǎng)絡、互操作、元數(shù)據(jù)等。,,１９９８年７月３０－３１日，美國的DOE/FNS共同聯(lián)合組織召開了關(guān)于“先進科學計算”的全國會議。會議強調(diào)科學模擬的重要性，希望應用科學模擬來攻克復雜的科學與工程難題。,,號召全國科學技術(shù)工程界更廣泛地使用高性能超級計算機，動員更多的人來從事軟件、算法、通信基礎設施、可視化系統(tǒng)的研究和開發(fā)。,,１９９８年９月，美國ＤＯＥ在全國范圍內(nèi)倡議實施“科學模擬計劃”(S

19、SP)，提出要加速“燃燒系統(tǒng)”與全球氣候系統(tǒng)“這兩大應用領域的科學模擬研究。并希望在以下五個方面的工作能得到全國的大力支持：,,算法，其它方法與庫技術(shù)；解決問題的環(huán)境與工具；分布式計算與協(xié)同計算環(huán)境；可視化處理與數(shù)據(jù)管理系統(tǒng)；系統(tǒng)體系結(jié)構(gòu)與平臺戰(zhàn)略研究。,,1999年初美國總統(tǒng)信息技術(shù)顧問委員會提出一項題為《21世紀的信息技術(shù)：對美國未來的大膽投資》的報告（即IT2計劃）。,,美國在2000年度財政預算中有關(guān)信息技術(shù)方面的投資達

20、3.66 億美元（增加28%），重點投資的三個領域是：①長期信息技術(shù)研究；②用于科學、工程和國家的高級計算；③信息革命的經(jīng)濟和社會意義研究。將在超級計算機、數(shù)學模擬和網(wǎng)絡等方面取利新的進步，開創(chuàng)一個新的邁向自然世界的窗口一使得計算作為科學發(fā)現(xiàn)的一種工具，而和理論及實驗具有同等的價值。,,數(shù)值方法和數(shù)值軟件過去50年的主要進展附錄,,Before 1940,Newton’s method; Gaussian elimination; Ga

21、uss quadrature; least squares fitting; Adams and Runge-Kutta formulas;Richardson extrapolation,1940-1970,floating point arithmetic; Fortran ; finite differences; finite elements; FFT; simplex algorithm; Monte Carlo; orth

22、ogonal linear algebra; spline function,,1970-2000,quasi-Newton iterations; adaptivity; stiff ODE solvers; software libraries; Matlab; multigrid; sparse and iterative linear algebra; spectral methods; interior point metho

23、ds,二.計算數(shù)學未來50年的展望,,我們將更多的通過聲音，而不是鍵盤向計算機傳遞信息，而計算機將更多地以圖象而不是數(shù)字反映結(jié)果。,,數(shù)值計算將更具有適應性、迭代性、靈活性。計算能力大得驚人。,,數(shù)值計算中更具智能性。,,求解線性方程組的浮點運算量會下降。,,Krylov型算法會有新的進展；條件預優(yōu)矩陣的確定、譜方法、PDE的時間步長會有新的突破。,,2000--2050,linear algebra in O(N2+eps) flop

24、s;multipole methods; breakthroughs in preconditioners, spectral methods, time stepping for PDE; fully intelligent, adaptive numerics; loss of determinism;speech and graphics everywhere…,參考文獻：,[1]．張鎖春：計算學是科技進步的重要推動力量---淺談

25、計算物理和高性能計算學。中國科學報， 1997/8/4 [2] . 張鎖春: 計算物理、科學計算、戰(zhàn)略計算， 計算數(shù)學通訊，2000.2 [3].