Analyzing the error bounds of multipole-based treecodes

ABSTRACT

The problem of evaluating the potential due to a set of particles is an important and time-consuming one. The development of fast treecodes such as the Barnes-Hut and Fast Multipole Methods for n-body systems has enabled large scale simulations in astrophysics [9, 10, 13] and molecular dynamics [1]. Coupled with efficient parallel processing, these treecodes are capable of yielding several orders of magnitude improvement in performance [6, 14, 15]. In addition, treecodes have applications in the solution of dense linear systems arising from boundary element methods [3, 4, 5, 11, 12]. Using a p-term multipole expansion, the FMM reduces the complexity of a single timestep from O(n²) to O(p²n) and Barnes-Hut method reduces it to O(p²n log n) for a uniform distribution.In this paper, we analyze the approximations introduced by these methods. We describe an algorithm that reduces the error significantly by selecting the multipole degree appropriately for different clusters. Furthermore, we show that for practical problem sizes, this increases the computational complexity marginally. We support our theoretical result with experiments in the context of particle simulations as well as boundary element methods. Our POSIX threads-based treecode yields excellent speedups on a 32 processor SGI Origin 2000, even for relatively small problems.

REFERENCES

• 1: J. A. Board, J. W. Causey, J. F. Leathrum, A. Windemuth, and K. Schulten. Accelerated molecular dynamics with the fast multipole algorithm. Chem. Phys. Let., 198:89, 1992.
• 2: Paul B. Callahan , S. Rao Kosaraju, A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.546-556, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129766]
• 3: R. Coifman, V. Rokhlin, and S. Wandzura. The fast multipole algorithm for the wave equation: A pedestrian prescription. IEEE Antennas and Propagation Magazine, 35(3), June, 1993.
• 4: N. Engheta, W. Murphy, V. Rokhlin, and M. Vassiliou. The fast multipole method for electromagnetic scattering problems. IEEE Transactions on Antennas and Propagation, 40(6), June, 1992.
• 5: Ananth Grama , Vipin Kumar , Ahmed Sameh, Parallel Hierarchical Solvers and Preconditioners for Boundary Element Methods, SIAM Journal on Scientific Computing, v.20 n.1, p.337-358, Aug. 1998 [doi>10.1137/S1064827596313322]
• 6: Ananth Grama , Vipin Kumar , Ahmed Sameh, Scalable parallel formulations of the Barnes-Hut method for n-body simulations, Parallel Computing, v.24 n.5-6, p.797-822, June 1998 [doi>10.1016/S0167-8191(98)00011-8]
• 7: L. Greengard. The Rapid Evaluation of Potential Fields in Particle Systems. MIT Press, 1987.
• 8: L. Greengard , V. Rokhlin, A fast algorithm for particle simulations, Journal of Computational Physics, v.73 n.2, p.325-348, December 1, 1987 [doi>10.1016/0021-9991(87)90140-9]
• 9: Neal Katz, Thomas Quinn, Edmund Bertschinger, and James M. Gelb. Formation of quasars at high redshift. Mon. Not. R. Astron. Soc., 270:L71-L74, 1994.
• 10: Neal Katz and Simon White. Hierarchical galaxy formation: overmerging and the formation of an x-ray cluster. Astrophysical Journal, 412(2):412-455, 1993.
• 11: K. Nabors , F. T. Korsmeyer , F. T. Leighton , J. White, Preconditioned, adaptive, multipole-accelerated iterative methods for three-dimensional first-kind integral equations of potential theory, SIAM Journal on Scientific Computing, v.15 n.3, p.713-735, May 1994 [doi>10.1137/0915046]
• 12: V. Rokhlin. Rapid solution of integral equations of classical potential theory. Journal of Computational Physics, 60:187 - 207, Sept 1985.
• 13: John Salmon and Michael S. Warren. Parallel out-of-core methods for n-body simulation. In 8th SIAM Conf. on Parallel Processing for Scientific Computing, 1997.
• 14: Jaswinder Pal Singh , Chris Holt , Takashi Totsuka , Anoop Gupta , John Hennessy, Load balancing and data locality in adaptive hierarchical N-body methods: Barnes-Hut, fast multipole, and radiosity, Journal of Parallel and Distributed Computing, v.27 n.2, p.118-141, June 1995 [doi>10.1006/jpdc.1995.1077]
• 15: M. S. Warren , J. K. Salmon, A parallel hashed Oct-Tree N-body algorithm, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.12-21, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169640]