Data Structures, Optimal Choice of Parameters, and Complexity Results for Generalized Multilevel Fast Multipole Methods in $d$ Dimensions
Data Structures, Optimal Choice of Parameters, and Complexity Results for Generalized Multilevel Fast Multipole Methods in $d$ Dimensions
Loading...
Files
Publication or External Link
Date
2003-04-04
Authors
Gumerov, Nail A.
Duraiswami, Ramani
Borovikov, Eugene A.
Advisor
Citation
DRUM DOI
Abstract
We present an overview of the Fast Multipole Method, explain the use of
optimal data structures and present complexity results for the algorithm.
We explain how octree structures and bit interleaving can be simply used
to create efficient versions of the multipole algorithm in $d$ dimensions.
We then present simulations that demonstrate various aspects of the
algorithm, including optimal selection of the clustering parameter, the
influence of the error bound on the complexity, and others. The use of
these optimal parameters results in a many-fold speed-up of the FMM, and
prove very useful in practice.
UMIACS-TR-2003-28