A Global Interpolator With Low Sample Rate for Multilevel Fast Multipole Algorithm

A new, improved version of a global interpolator utilizing trigonometric polynomials is presented for the high-frequency multilevel fast multipole algorithm. The number of required points to sample the outgoing and incoming field patterns is low, almost half in some levels, compared with the earlier published versions. Compared with local interpolators based on Lagrange interpolating polynomials, the proposed technique performs even more favorably and reduces the number of sample points by a factor of eight. The numerical examples demonstrate that the interpolator allows full numerical accuracy control during the aggregation and disaggregation phases, regardless of the number of the levels in the octree.