Computational and memory complexities of Greengard-Rokhlin's fast multipole algorithm

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(L log(2) L) and O(L log L), respectively. The computational complexity-of GRFMA is higher than that of the multilevel fast multipole algorithm.