A fast algorithm for three-dimensional electrostatics analysis: Fast Fourier Transform on Multipoles (FFTM)

Abstract

In this paper, we propose a new fast algorithm for solving large problems using the boundary element method (BEM). Like the fast multipole method (FMM), the speed-up in the solution of the BEM arises from the rapid evaluations of the dense matrix-vector products required in iterative solution methods. This fast algorithm, which we refer to as fast Fourier transform on multipoles (FFTM), uses the fast Fourier transform (FFT) to rapidly evaluate the discrete convolutions in potential calculations via multipole expansions. It is demonstrated that FFTM is an accurate method, and is generally more accurate than FMM for a given order of multipole expansion (up to the second order). It is also shown that the algorithm has approximately linear growth in the computational complexity, implying that FFTM is as efficient as FMM. © 2004 John Wiley and Sons, Ltd.