I read the following two papers a few weeks ago and found the ideas to be very similar to Rokhlin’s generalized FMM.

  • References:
    • Hao Gang Wang, Chi Hou Chan, Leung Tsang, “A New Multilevel Green’s Function Interpolation Method for Large-Scale Low Frequency EM Simulations,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol-24, No. 9, September 2005, pp1427-1443.
    • Hao Gang Wang, Chi Hou Chan, “The Implementation of Multilevel Green’s Function Interpolation Method for Full-Wave Electromagnetic Problems,” IEEE Trans. Antennas and Propagation, Vol-55, No. 5, May 2007, pp1348–1358
  • Comments

    • The first paper discusses the method for low frequency, almost static, problems and the second, extends the method to full wave problems.
    • The essential idea is very similar, in fact almost the same, as in Rokhlin’s generalized fast multipole method. They can be summarized as follows:
      • Single level approach: the objects are enclosed in a cube. The cube is then divided into to a grid of smaller cubes. For each cube, the sources are projected on to an appropriate grid through interpolation (Lagrange). Interaction between two well separated cubes are computed as follows: the Green’s function is evaluated at the corresponding grid in the field cube, with sources at the source grid. The computed Green’s function values are then interpolated back to the actual observation points.
      • The naive multilevel scheme is identical to the naive multilevel FMM outlined in the 1995(?) paper by Boeing group, I think. Essentially compute the equivalent sources directly for each cube and then follow the same computation.
      • The more sophisticated multilevel scheme uses another interpolation scheme to map the equivalent sources: it takes a set of already mapped sources and interpolates the values to the corresponding nodes at the parent level.
    • This is essentially a fast multipole method without explicitly using multipoles. The interpolation operators correspond to the shifting operators in conventional FMM. The Green’s function matrices correspond to the translation matrices.
    • In the second paper, instead of Lagrange interpolation, they use radial basis functions. They construct a numerically orthogonal set of radial basis functions. This is an interesting idea.
    • In the second paper, they have to increase the number of samples at each level. This is in agreement with the requirement of larger number of multipoles in MLFMM. To reduce the computational cost, they use QR decomposition to compress it.

On the whole, it is an interesting academic work. Without the QR compression, the algorithm is not very efficient, which raises the question if there is any significant advantage to this method over IES3 or Rokhlin’s generalized FMM. My guess is that the use of radial basis functions could make it faster than Rokhlin’s idea, which used Lagrange interpolation, because of fewer sampling points. (I am not sure if they are aware of this work though.)