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(N1.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(K2) 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.
. FAST INTERPOLATION FOR MULTILEVEL FAST MULTIPOLE METHOD[J]. Mathematica Numerica Sinica, 2011, 33(2): 145-156.
Greengard L, Rokhlin V. A fast algorithm for particle simulations[J]. J. Comput. Phys., 1987, 73(2): 325-348.
Rokhlin V. Rapid solution of integral equations of scattering theory in two dimensions[J]. J. Comput. Phys., 1990, 86(2): 414-439.
Chew W C, Jin J M, etc., Fast and efficeint Algorithms for computational electromagnetics[M]. New York, NY: Artech House, 2001, 39-61.
Velamparambil S, Chew W C. A fast polynomial representation for the translation operators of an MLFMA[J]. Microwave and Optical Technology Letters, 2001, 28(5): 298-303.
Yarvin N, Rokhlin V. An improved fast multipole algorithm for potential fields on one-dimensional structures[J]. SIAM J. Numer. Anal., 1999, 36(2): 629-666.
Healy D, Rockmore D, etc., FFTs for the 2-sphere: improvements and variations[J]. J. Fourier Anal. Appl., 2003, 9(4): 341-385.
Dutt A, Gu M, Rokhlin V. Fast algorithms for polynomial interpolation, integration, and differ-entiation[J]. SIAM J. Numer. Anal., 1996, 33(55): 1689-1711.
Darve E. The fast multipole method: numerical implementation[J]. J. Comput. Phys., 2000, 160(1): 195-240.
Holmes S, Featherstone W. A unified approach to the Clenshaw summation and the recursive computation of very high degree and order normalised associated Legendre functions[J]. Journal of Geodesy, 2002, 76(5): 279-299.
Alpert B, Chien R. A Fast spherical filter with uniform resolution[J]. J. Comput. Phys., 1997, 136(2):580-584.
Rokhlin V, Tygert M. Fast algorithms for spherical harmonic expansions[J], SIAM J. Sci. Comput., 2006, 27(6): 1903-1928.
Berrut J P, Trefethen L N. Barycentric Lagrange interpolation[J]. SIAM Rev., 2004, 46(3): 501-517.