For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Computational and Memory Complexities of Greengard-Rokhlin's Fast Multipole Algorithm
Norimasa NAKASHIMA Mitsuo TATEIBA
IEICE TRANSACTIONS on Electronics
Publication Date: 2005/07/01
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Electromagnetic Theory
Greengard-Rokhlin's algorithm, fast multipole method, computational complexity, memory complexity,
Full Text: PDF>>
This paper describes an estimation of the computational and memory complexities of Greengard-Rokhlin's Fast Multipole Algorithm (GRFMA). GRFMA takes a quad tree structure and six calculation processes. We consider a perfect a-ary tree structure and the number of floating-point operations for each calculation process. The estimation for both complexities shows that the perfect quad tree is the best and the perfect binary tree is the worst. When we apply GRFMA to the computation of realistic problems, volume scattering are the best case and surface scattering are the worst case. In the worst case, the computational and memory complexities of GRFMA are O(Llog2 L) and O(Llog L), respectively. The computational complexity of GRFMA is higher than that of the multilevel fast multipole algorithm.