中文摘要：

多层快速多极子方法（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.