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

《快速多极子方法的并行技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、快速多极子方法的并行技术国家973项目——高性能科学计算研究大规模并行计算研究纲要FMMDataStructuresParallelization纲要FMMDataStructuresParallelizationFMMinComputationalElectromagneticsEFIEMFIECFIEGreen函数积分方程的离散RWG矢量基函数MOM离散Rao-Wilson-GlissonMethodofMomentsSurfaceisDiscretizedintoPatches(BasisFunctions)BasisFunctionsInteractthr

2、oughtheGreen’sFunctionGeneratesaDenseMethodofMomentsMatrixPulse线性系统：Mx=sM是N×N矩阵，x、s是N矢量●Directsolution(Gausselimination,LUDecomposition,SVD,…)空间复杂度为O(N2)，需要O(N3)次运算；●Iterativemethods,空间复杂度仍为O(N2)，如果K(k<

3、riable,16generationsofMoore’LawbeforeaO(N2)algorithmwascomparablewithaO(N)algorithm—1GBRAM=10243=1,073,741,824bytes=>largestN=32,768●Finding:快速矩阵乘向量的算法(NlogN)；并行实施。FastMultipoleMethods(FMM)IntroducedbyRokhlin&Greengardin1987Calledoneofthe10mostsignificantadvancesincomputingof20thcentu

4、rySpeedsupmatix-vectorproducts(sums)ofaparticulartype以上求和要求O(MN)运算复杂度对给定的精度，FMM可以获得O(M+N)运算复杂度可以加速matix-vectorproducts，使O(N2)变为O(NlogN)加速线性系统求解，如果用迭代方法，k步收敛，每步用矩阵矢量相乘，使计算复杂度由O(N3)变为O(kNlogN)FMM:ApplicationMolecularandStellardynamics—computationofforcefieldsanddynamicsSolutionofacousti

5、calscatteringproblems—HelmholtzEquationElectromagneticWaveScattering—Maxwell’sEquationsFluidMechanics:Potentialflow,vertexflow—Laplace/PoissonEquationsFMM:Fundament格林函数的加法定理jlpl平面波展开jl_—第一类球面Bessel函数hl(2)—第二类球面Hankel函数Pl—Legendre多项式注意到lz时，函数jl(z)衰减非常快，而

6、hl(2)(z)递增非常快。当d<

7、盒子中的基函数。M2M,M2L,L2L：聚集–转移–发散M:多极子展开L:局部展开FMM由于E2(n)和E3(n)是互补的，因此对任意的n,FMMAlgorithmStep1M2MStep2M2LStep3L2LSummationMLFMMAlgorithmUpwardPass:mergescatteringmatricesDownwardPass:constructsplittingandexchangematricesFinalSummationBasedOn:◆HierarchicalGrouping◆DataStructureL2LM2MM2MM2LM2L

8、M2LMu