Computational and Memory Complexities of Greengard-Rokhlin's Fast Multipole Algorithm

Norimasa NAKASHIMA  Mitsuo TATEIBA  

IEICE TRANSACTIONS on Electronics   Vol.E88-C   No.7   pp.1516-1520
Publication Date: 2005/07/01
Online ISSN: 
DOI: 10.1093/ietele/e88-c.7.1516
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>>
Buy this Article

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.