Hachul, Stefan and Jünger, Michael (2006) A Provably Fast Multipole Method.
Technical Report , 25 p.

Abstract

The evaluation of potential or force fields in systems of N particles whose interactions are Coulombic or gravitational is very important for several applications in natural science, applied mathematics, and computer science. A naive direct calculation of the interactions needs Theta(N^2) time per time step which is inappropriate for large systems.Therefore, fast hierarchical algorithms (called tree codes) are used that approximate the pairwise interactions in the systems. We present a new multipole-based tree code that runs in O(N) time in the best case and in O(N log N) time in the worst case. This is an improvement in comparison with existing tree codes: Few of them run in Theta(N log N) time. Others are O(N) or O(N log N) in the best case but quadratic or even unbounded in the worst case. Our practical experiments indicate that the new multipole method is faster than several popular hierarchical N -body simulation algorithms for both uniform and highly non-uniform particle distributions.

Actions:

Download:	Postscript - Submitted Version Download (1MB) | Preview
Download:	PDF - Submitted Version Download (2MB) | Preview
Editorial actions:	View Item (Login required)