有效的數(shù)值算法

幾種有效的數(shù)值算法

報(bào)告人：王武

中科院超級(jí)計(jì)算中心Email:wangwu@

20010年5月

1FastAlgorithmyearmethodreferencestorageflops1947GEVonNeumann,Goldstinen5n71950SORYoungn3n4logn1971CGReidn3n3.5logn1984MGBrandtn3n31987FMMGreengard,Rokhlinn2lognn2lognnnIfn=64,thistableimpliesanoverallreductioninflopsof160million,whichmeetstheMoore’sLaw!(doublingin1.5year)SciDACInitiative,DOE,CSGF,2005n21.快速多極子方法快速多極子方法克服了多粒子模擬中最大的瓶頸：精確計(jì)算N個(gè)粒子之間通過萬有引力或靜電力的相互作用（比如星系中的星體，或蛋白質(zhì)中的分子）需要O(N2)的量級(jí)。而FMM達(dá)到了O(N)的量級(jí)。FMM顯著的優(yōu)點(diǎn)之一是它可以任意調(diào)整精度這種算法通過多極展開（空間的粒子或質(zhì)點(diǎn)、偶極子，四重極子等等）來近似遠(yuǎn)處的粒子組對(duì)近端的局部粒子組的作用一個(gè)遞歸劃分的空間用來描述隨距離增大的更大的組FastMultipoleMethod(FMM),1987LGreengardVRokhlin,YaleUniversity3靜電場(chǎng)和引力場(chǎng)位勢(shì)的多極子展開矩陣向量乘積形式N體問題4FMM的應(yīng)用綜述1ElectromagneticScatteringStellarClustersProteinFolding5FMM的應(yīng)用綜述2RBFInterpolationVortexParticleMethodforTurbulenceAcousticPressurearoungtheWingFM-BEMforCompositeMaterials6渦粒子方法Navier-Stokes方程Gauss型基函數(shù)7多極子展開Helmholtz型Laplace型Gauss型82.MonteCarlo方法基于隨機(jī)模擬的計(jì)算方法確定性問題。建立概率模型，再進(jìn)行隨機(jī)抽樣觀察，其算術(shù)平均即為所求解的近似估計(jì)。精度可用估計(jì)值的標(biāo)準(zhǔn)誤差表示。例如計(jì)算積分（多重積分，與維數(shù)無關(guān)）、計(jì)算面積（圓周率）隨機(jī)性問題。根據(jù)物理情況的概率法則，用計(jì)算機(jī)抽樣試驗(yàn)。例如中子在介質(zhì)中的擴(kuò)散、隨機(jī)服務(wù)系統(tǒng)中的排隊(duì)、動(dòng)物的生態(tài)競(jìng)爭(zhēng)（MCNP是LosAlamos實(shí)驗(yàn)室開發(fā)的大型蒙特卡羅程序，可計(jì)算中子、光子和電子的聯(lián)合輸運(yùn)問題以及臨界問題）Π/4=S(round)/S(square)Π=4N(round)/N(square)N=no.ofrandompointsTheMetropolisAlgorithmforMonteCarloJohnvonNeumann,etal,LosAlamosLab,19469收斂性誤差對(duì)于獨(dú)立同分布隨機(jī)序列，由中心極限定理可知MonteCarlo方法求積分任何一個(gè)積分，都可看作某個(gè)隨機(jī)變量的期望值，因此，可以用這個(gè)隨機(jī)變量的平均值來近似它f(x):概率密度函數(shù)正態(tài)分布概率誤差103.單純形方法具有約束條件的線性規(guī)劃問題如何求最優(yōu)解？單純形方法的基本思想是：從可行域的某一個(gè)極點(diǎn)出發(fā)，迭代到另一個(gè)極點(diǎn)，并使目標(biāo)函數(shù)的值有所改善，直到找出有無最優(yōu)解時(shí)為止該方法用到了單純形的概念，單純形是指N維中的N+1個(gè)頂點(diǎn)的凸包，是一個(gè)多胞體(比如直線上的一個(gè)線段，平面上的一個(gè)三角形，三維空間中的一個(gè)四面體）單純形法盡管理論上講效果是指數(shù)衰減的，但在實(shí)踐中卻是高度有效的在線性空間中極大化Z

極大化并滿足約束SimplexMethodforLinearProgrammingGeorgeDantzig,RANDCorporation,1947其中114.Krylov子空間迭代法Krylov子空間迭代法是用來求解形如Ax=b的方程組，A是一個(gè)NxN的矩陣，當(dāng)N充分大時(shí)，直接計(jì)算x=A-1b變得非常困難。Krylov方法則巧妙地將其變?yōu)槿缦碌问角蠼?。Kx(i+1)=Kx(i)+b-Ax(i)這里的K是一個(gè)構(gòu)造出來的接近于A的矩陣，而迭代形式的算法的妙處在于，它將復(fù)雜問題化簡(jiǎn)為逐步的易于計(jì)算的子步驟。當(dāng)A是對(duì)稱矩陣時(shí)，Lanczos找到了生成子空間K的正交基的方法。Hestenes和Stiefel提出了共軛梯度法。后來的GMRES、BiCGStab等改進(jìn)并擴(kuò)展了這些算法。Krylov子空間:Km=span{r0,Ar0,…,Am-1r0},rm=b-Ax(m)伴隨迭代法的是預(yù)條件子：構(gòu)造M，用迭