摘要
多层快速多极子方法(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.
出处
《计算数学》
CSCD
北大核心
2011年第2期145-156,共12页
Mathematica Numerica Sinica
基金
国家自然科学基金(10972215
60873113)
国家高技术研究发展计划(2009AA01A134
2010AA012301)
国家重点基础研究发展计划(2010CB832702)资助项目
关键词
积分方程
多层快速多极子方法
转移项
快速Lagrange插值
快速谱插值
integral equation
multilevel fast multipole method
translation term
fast Lagrange interpolation
fast spectrum interpolation
