Computational and Memory Complexities of Greengard-Rokhlin's Fast Multipole Algorithm
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Electronics Vol.E88-C No.7 pp.1516-1520
- Publication Date
- 2005/07/01
- Publicized
- Online ISSN
- DOI
- 10.1093/ietele/e88-c.7.1516
- Type of Manuscript
- LETTER
- Category
- Electromagnetic Theory
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Norimasa NAKASHIMA, Mitsuo TATEIBA, "Computational and Memory Complexities of Greengard-Rokhlin's Fast Multipole Algorithm" in IEICE TRANSACTIONS on Electronics,
vol. E88-C, no. 7, pp. 1516-1520, July 2005, doi: 10.1093/ietele/e88-c.7.1516.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/electronics/10.1093/ietele/e88-c.7.1516/_p
Copy
@ARTICLE{e88-c_7_1516,
author={Norimasa NAKASHIMA, Mitsuo TATEIBA, },
journal={IEICE TRANSACTIONS on Electronics},
title={Computational and Memory Complexities of Greengard-Rokhlin's Fast Multipole Algorithm},
year={2005},
volume={E88-C},
number={7},
pages={1516-1520},
abstract={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.},
keywords={},
doi={10.1093/ietele/e88-c.7.1516},
ISSN={},
month={July},}
Copy
TY - JOUR
TI - Computational and Memory Complexities of Greengard-Rokhlin's Fast Multipole Algorithm
T2 - IEICE TRANSACTIONS on Electronics
SP - 1516
EP - 1520
AU - Norimasa NAKASHIMA
AU - Mitsuo TATEIBA
PY - 2005
DO - 10.1093/ietele/e88-c.7.1516
JO - IEICE TRANSACTIONS on Electronics
SN -
VL - E88-C
IS - 7
JA - IEICE TRANSACTIONS on Electronics
Y1 - July 2005
AB - 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.
ER -
English
