Premium
A fast algorithm for three‐dimensional electrostatics analysis: fast Fourier transform on multipoles (FFTM)
Author(s) -
Ong E. T.,
Lee K. H.,
Lim K. M.
Publication year - 2004
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/nme.1081
Subject(s) - fast multipole method , fast fourier transform , multipole expansion , algorithm , boundary element method , fourier transform , discrete fourier transform (general) , prime factor fft algorithm , split radix fft algorithm , mathematics , computer science , fractional fourier transform , mathematical analysis , fourier analysis , physics , finite element method , quantum mechanics , thermodynamics
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. Copyright © 2004 John Wiley & Sons, Ltd.