快速多極子方法并行的技術(shù)課件

快速多極子方法并行的技術(shù)國家973項(xiàng)目高性能科學(xué)計(jì)算研究大規(guī)模并行計(jì)算研究快速多極子方法的并行技術(shù)馮仰德王武遲學(xué)斌中科院計(jì)算機(jī)網(wǎng)絡(luò)信息中心超級(jí)計(jì)算中心yufengccas207年2月5日綱要FMM·DatastructuresParallelization綱要●FMMDatastructuresParallelizationFMMinComputationalelectromagneticsefietL()=tE(r,rES,L()=jkn](I+vv/k2)8(r,r,).J(r,)dS;mfietJ(r)/2+tn×K④J)=tnxH(r),K(=LJ(r)Vg(r,r,)dSCFIECFIE=aEFIE+(I-anMFTerc函數(shù)g(r,r)=ek/4x|r-r積分方程的離散Rao-Wilson-GlissonRWG天量基函數(shù)J(r)=∑ifr)f(r=lip;(r)/2A.p(r)=r-r,freTpi(r)/2A,p(r)=r-r,ifr∈TMOM離散么mn-m,m=1.2,N.n=1fn(r)1aL()+(1-a)f(r)/2+n×K(f,)}dSvm=Lf(r).ae(r)+(1-a)nnxH'(r)ds.MethodofmomentsSurfaceisDiscretizedintoPatches(BasisFunctions)PulseBasisFunctionsInteractthroughtheGreensFunctionf(r)GeneratesaDenseMethodofmomentsmatrixznd=Vi(i=5.]G(r,r)/(r)ds線性系統(tǒng):Mx=sM是NXN矩陣,x、s是N矢量DIrectsolution(Gausselimination,LUDecomposition,SVD,)空間復(fù)雜度為ON2),需要QN次運(yùn)算●|Iterativemethods,空間復(fù)雜度仍為OP),如果K(K<<N)步收斂,每步需要的矩陣乘向量的運(yùn)算為O(N)MooreLaw:processorspeeddoublesevery18monthsamillionvariable,16generationsofMoore'Lawbeforeao(n2)algorithmwascomparablewithao(n)algorithm1GBRAN=10243=1073,741,824bytes=largestN=32,768●Finding:快速矩陣乘向量的算法(MogN并行實(shí)施。FastMultipoleMethods(FMM)IntroducedbyRokhlinGreengardin1987Calledoneofthe10mostsignificantadvancesincomputingof20thcenturySpeedsupmatix-vectorproducts(sums)ofaparticulartype(x1-x),(s;}=nla;以上求和要求O(MN運(yùn)算復(fù)雜度對給定的精度,FMM可以獲得OM+N)運(yùn)算復(fù)雜度可以加速matx-vectorproducts,使O(N2)變?yōu)镺(NogN)·加速線性系統(tǒng)求解,如果用迭代方法,k步收斂,每步用矩陣矢量相乘,使計(jì)算復(fù)雜度由O(N)變?yōu)镺(kNlogN)FMM:ApplicationMolecularandStellardynamicscomputationofforcefieldsanddynamicsSolutionofacousticalscatteringproblems-helmholtzequationElectromagneticWaveScatteringMaxwell'sequationsFluidMechanics.PotentialflowvertexflowLaplace/poissonequationsFMM:Fundament格林函數(shù)的加法定理j—第一類球面Bessel函數(shù)jalr+dlh2-第二類球面Hankel函數(shù)認(rèn)∑(-1)(21+D)j(kd)h2(k)P(d●r)dLegendre多項(xiàng)式注意到/<2,函數(shù)z廂加2(z幅值大致保持為常數(shù);卜時(shí),函數(shù)(2)減非?？於?z遞增非常快。當(dāng)d<<r時(shí),上式在保證精度的情況下截?cái)?。則上式可以寫為ejelr+d∑(-1)(21+Djk)2(k)Pdr)L=kd+cln(kd+丌)+dKd源點(diǎn)到觀察點(diǎn)的最大半徑c是一個(gè)依賴希望精度的常數(shù)1最小的相對誤差小于0.1j平面波展開相對誤差小于106=10準(zhǔn)確到雙精度4I(J",(kd)P(dr)=k,/p,kr)d'k66、節(jié)制使快樂增加并使享受加強(qiáng)。——德謨克利特

67、今天應(yīng)做