多层快速多极子方法的快速插值  

FAST INTERPOLATION FOR MULTILEVEL FAST MULTIPOLE METHOD

作　　者：王武[1] 冯仰德[1] 迟学斌[1] 

机构地区：[1]中国科学院计算机网络信息中心超级计算中心,北京100190

出　　处：《计算数学》2011年第2期145-156,共12页Mathematica Numerica Sinica

基　　金：国家自然科学基金(10972215;60873113);国家高技术研究发展计划(2009AA01A134;2010AA012301);国家重点基础研究发展计划(2010CB832702)资助项目

摘　　要：多层快速多极子方法(MLFMM)可用来加速迭代求解由Maxwell方程组或Helmholtz方程导出的积分方程,其复杂度理论上是O(N log N),N为未知量个数.MLFMM依赖于快速计算每层的转移项,以及上聚和下推过程中的层间插值.本文引入计算类似N体问题的一维快速多极子方法(FMM1D).基于FMM1D的快速Lagrange插值算法可将转移项的计算复杂度由O(N^(1.5))降低到O(N).运用FMM1D与FFT混合的快速谱插值算法可将层间插值的计算复杂度由O(K^2)降低到O(K log K),K为插值取样点数.数值结果显示了基于这两种快速插值的MLFMM具有近似线性的时间复杂度.Multilevel fast multipole method（MLFMM）can be used to accelerate the iterative solution of integral equation deduced from Maxwell equations or Helmholtz-type equation, with a theoretical complexity ofO（N log N）,where N is the number of unknowns.MLFMM depends on fast calculating the translation term at each level,and interpolations between levels during upward and downward pass phases.The one-dimentional fast multipole method （FMM1D）similar to which used in N-body problem is introduced in this paper. Fast Lagrange interpolation algorithm based on FMM1D can reduce the computing time of translation operator fromO（N^（1.5））toO（N）.Fast spectrum interpolation with a hybrid FFT-FMM1D method can also reduce the computing complexity of interpolations between levels fromO（K^2）toO（K log K）,where K is the number of sample points.The numerical results of MLFMM based on these two fast inperpolation methods have near linear time performances and accurate solutions.

关 键 词：积分方程 多层快速多极子方法 转移项 快速Lagrange插值 快速谱插值 

分 类 号：O241.3[理学—计算数学]