快速多极子方法并行的技术课件

快速多极子方法并行的技术国家973项目高性能科学计算研究大规模并行计算研究快速多极子方法的并行技术冯仰德王武迟学斌中科院计算机网络信息中心超级计算中心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函数g(r,r)=ek/4x|r-r积分方程的离散Rao-Wilson-GlissonRWG天量基函数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线性系统:Mx=sM是NXN矩阵,x、s是N矢量DIrectsolution(Gausselimination,LUDecomposition,SVD,)空间复杂度为ON2),需要QN次运算●|Iterativemethods,空间复杂度仍为OP),如果K(K<<N)步收敛,每步需要的矩阵乘向量的运算为O(N)MooreLaw:processorspeeddoublesevery18monthsamillionvariable,16generationsofMoore'Lawbeforeao(n2)algorithmwascomparablewithao(n)algorithm1GBRAN=10243=1073,741,824bytes=largestN=32,768●Finding:快速矩阵乘向量的算法(MogN并行实施。FastMultipoleMethods(FMM)IntroducedbyRokhlinGreengardin1987Calledoneofthe10mostsignificantadvancesincomputingof20thcenturySpeedsupmatix-vectorproducts(sums)ofaparticulartype(x1-x),(s;}=nla;以上求和要求O(MN运算复杂度对给定的精度,FMM可以获得OM+N)运算复杂度可以加速matx-vectorproducts,使O(N2)变为O(NogN)·加速线性系统求解,如果用迭代方法,k步收敛,每步用矩阵矢量相乘,使计算复杂度由O(N)变为O(kNlogN)FMM:ApplicationMolecularandStellardynamicscomputationofforcefieldsanddynamicsSolutionofacousticalscatteringproblems-helmholtzequationElectromagneticWaveScatteringMaxwell'sequationsFluidMechanics.PotentialflowvertexflowLaplace/poissonequationsFMM:Fundament格林函数的加法定理j—第一类球面Bessel函数jalr+dlh2-第二类球面Hankel函数认∑(-1)(21+D)j(kd)h2(k)P(d●r)dLegendre多项式注意到/<2,函数z厢加2(z幅值大致保持为常数;卜时,函数(2)减非常快而(z递增非常快。当d<<r时,上式在保证精度的情况下截断。则上式可以写为ejelr+d∑(-1)(21+Djk)2(k)Pdr)L=kd+cln(kd+丌)+dKd源点到观察点的最大半径c是一个依赖希望精度的常数1最小的相对误差小于0.1j平面波展开相对误差小于106=10准确到双精度4I(J",(kd)P(dr)=k,/p,kr)d'k66、节制使快乐增加并使享受加强。——德谟克利特

67、今天应做