《快速多极子方法并行的技术》由会员分享，可在线阅读，更多相关《快速多极子方法并行的技术（60页珍藏版）》请在金锄头文库上搜索。
1、快速多极子方法的并行技术,冯仰德 王武 迟学斌 中科院计算机网络信息中心 超级计算中心 2007年2月5日,国家973项目高性能科学计算研究 大规模并行计算研究,纲要,FMM Data Structures Parallelization,纲要,FMM Data Structures Parallelization,FMM in Computational Electromagnetics,EFIE MFIE CFIE Green函数,积分方程的离散,RWG矢量基函数 MOM 离散,Rao-Wilson-Glisson,Method of Moments,Surface is Discret
2、ized into Patches (Basis Functions),Basis Functions Interact through the Greens Function,Generates a Dense Method of Moments Matrix,线性系统：,Mx=s M是NN矩阵，x、s是N矢量 Direct solution (Gauss elimination,LU Decomposition,SVD,) 空间复杂度为O(N2) ，需要O(N3)次运算； Iterative methods,空间复杂度仍为O(N2)，如果K(k largest N =32,768 Find
3、ing:快速矩阵乘向量的算法(NlogN)； 并行实施。,Fast Multipole Methods(FMM),Introduced by Rokhlin &Greengard in 1987 Called one of the 10 most significant advances in computing of 20th century Speeds up matix-vector products (sums) of a particular type 以上求和要求O(MN)运算复杂度 对给定的精度，FMM可以获得O(M+N)运算复杂度 可以加速matix-vector produc
4、ts ，使O(N2)变为O(NlogN) 加速线性系统求解，如果用迭代方法，k步收敛，每步用矩阵矢量相乘，使计算复杂度由O(N3)变为O(kNlogN),FMM:Application,Molecular and Stellar dynamics computation of force fields and dynamics Solution of acoustical scattering problems Helmholtz Equation Electromagnetic Wave Scattering Maxwells Equations Fluid Mechanics:Potent
5、ial flow,vertex flow Laplace/Poisson Equations,FMM: Fundament,格林函数的加法定理 jlpl平面波展开,jl_第一类球面Bessel函数 hl(2) 第二类球面Hankel函数 Pl Legendre多项式,注意到lz时，函数jl(z)衰减非常快，而hl(2)(z)递增非常快。当dr时，上式在保证精度的情况下截断。则上式可以写为：,Kd-源点到观察点的最大半径 c-是一个依赖希望精度的常数 =1 最小的相对误差小于0.1 =5 相对误差小于10-6 =10 准确到双精度,Fast Multipole Basics,直接求解：,分解：,
6、复杂度：O(MN),复杂度：O(pN+pM),cm,FMM形式的矩阵向量乘积,近场部分,远场部分,电磁场积分方程的多极子展开,FMM, 聚集过程，将基函数聚集成平面波函数，其结果表示K个平面波,转移过程，将得到的x1 平移到另一个盒子的中心，其结果表示该盒子中心的K个平面波,发散过程，将得到的x2发散到盒子中的基函数。,M2M , M2L , L2L： 聚集 转移 发散 M: 多极子展开 L: 局部展开,FMM,由于E2(n)和E3(n)是互补的，因此对任意的n,FMM Algorithm,Step1 M2M,Step2 M2L,Step3 L2L,Summation,MLFMM Algori
7、thm,Upward Pass: merge scattering matrices Downward Pass: construct splitting and exchange matrices Final Summation,Based On: Hierarchical Grouping Data Structure,L2L,M2M,M2M,M2L,M2L,M2L,Multilevel Multipole Operators,Finest Level,Finest - 1 Level,L2L,Up Tree,Across Tree,Down Tree,MLFMM Algorithm Up
8、ward Pass,Step1: 在最细的层盒子求解远场展开系数，xiE1(n,l),得到C(n,l)或 ，这也可以用于xiE3(n,l) Step2:对于l=L-1,2,从step1得到值进行递归得到。同样适合xiE3(n,l) 结果：得到分层组聚集系数,MLFMM Algorithm Downward Pass,Step1:l=2,L递归进行E4 Step2:,任意一个非空组自身加上其邻接组最多可有3d个，其父组及父组的邻接组最多可形成3d2d，因此次相邻数目最多为p=3d(2d-1)；三维是189，二维是27，一维是3。,局部到局部的转移，E3(n,l)和E4(n,l+1)产生E3(n,l+1),结果：可以得到各分层组的转移系数,
