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

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

2、數(shù)值方法。,今天的數(shù)值計(jì)算方法，無論從形式到內(nèi)容，還是從工具到效果，已遠(yuǎn)非半世紀(jì)前Von Neumann、Lax等先驅(qū)們所處的環(huán)境和條件了，計(jì)算機(jī)技術(shù)和應(yīng)用軟件的發(fā)展，讓計(jì)算數(shù)學(xué)展開了雙翼。許多迅速發(fā)展的其他學(xué)科和社會(huì)進(jìn)步給計(jì)算數(shù)學(xué)的發(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、這里主要談二個(gè)方面：從計(jì)算物理的發(fā)展過程來看計(jì)算數(shù)學(xué)的過去；計(jì)算數(shù)學(xué)的未來50年.[1--3].,一. 計(jì)算數(shù)學(xué)發(fā)展的歷史回顧,,2,1. 從計(jì)算物理談起,計(jì)算數(shù)學(xué)的發(fā)展與科學(xué)工程計(jì)算是緊密相聯(lián)的，計(jì)算數(shù)學(xué)的發(fā)展歷史也就是與其他學(xué)科結(jié)合，利用計(jì)算機(jī)不斷形成新的理論及數(shù)值方法并不斷形成新的學(xué)科的歷史，例如：“計(jì)算物理”。,１９５９年５月美國總統(tǒng)發(fā)布命令，可以揭開曼哈頓計(jì)劃的內(nèi)幕，部分內(nèi)容可以解密。故以“計(jì)算物理方法”叢書的名義陸續(xù)編輯出版

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20、3.66 億美元（增加28%），重點(diǎn)投資的三個(gè)領(lǐng)域是：①長期信息技術(shù)研究；②用于科學(xué)、工程和國家的高級計(jì)算；③信息革命的經(jīng)濟(jì)和社會(huì)意義研究。將在超級計(jì)算機(jī)、數(shù)學(xué)模擬和網(wǎng)絡(luò)等方面取利新的進(jìn)步，開創(chuàng)一個(gè)新的邁向自然世界的窗口一使得計(jì)算作為科學(xué)發(fā)現(xiàn)的一種工具，而和理論及實(shí)驗(yàn)具有同等的價(jià)值。,,數(shù)值方法和數(shù)值軟件過去50年的主要進(jìn)展附錄,,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,二.計(jì)算數(shù)學(xué)未來50年的展望,,我們將更多的通過聲音，而不是鍵盤向計(jì)算機(jī)傳遞信息，而計(jì)算機(jī)將更多地以圖象而不是數(shù)字反映結(jié)果。,,數(shù)值計(jì)算將更具有適應(yīng)性、迭代性、靈活性。計(jì)算能力大得驚人。,,數(shù)值計(jì)算中更具智能性。,,求解線性方程組的浮點(diǎn)運(yùn)算量會(huì)下降。,,Krylov型算法會(huì)有新的進(jìn)展；條件預(yù)優(yōu)矩陣的確定、譜方法、PDE的時(shí)間步長會(huì)有新的突破。,,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…,參考文獻(xiàn)：,[1]．張鎖春：計(jì)算學(xué)是科技進(jìn)步的重要推動(dòng)力量---淺談

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