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

多层快速多极子方法(MLFMM)可用来加速迭代求解由Maxwell方程组或Helmholtz方程导出的积分方程,其复杂度理论上是O(NlogN),N为未知量个数.MLFMM依赖于快速计算每层的转移项,以及上聚和下推过程中的层间插值.本文引入计算类似N体问题的一维快速多极子方法(FMM1D).基于FMM1D的快速Lagr...

FAST INTERPOLATION FOR MULTILEVEL FAST MULTIPOLE METHOD

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 of O(N logN), 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 from O(N^1.5) to O(N). Fast spectrum interpolation with a hybrid FFT-FMM1D method can also reduce the computing complexity of interpolations between levels from O(K²) to O(K logK), 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.