Performing Interpolation and Anterpolation Entirely by Fast Fourier Transform in the 3-D Multilevel Fast Multipole Algorithm

The fast multipole methods are used for solving a scalar acoustic or vector electromagnetic wave equation by integral equation methods with a large number of unknowns. In this paper a new method is presented for performing interpolation and anterpolation in both spherical coordinates θ and φ by FFT in the three-dimensional (3-D) multilevel fast multipole algorithm (MLFMA). The key idea is to approximate functions on the unit sphere by truncated Fourier series in two variables rather than by the usual spherical harmonics. The proposed method is exact in interpolating and anterpolating and has the high numerical efficiency of FFT. The method is numerically compared to the method of performing interpolation and anterpolation using Lagrangian interpolation, which presently is probably the fastest method for those operations, and the results suggest that the proposed new method is equally or more efficient, depending on the desired accuracy.