A Provably Fast Multipole Method

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


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.

Download: [img] Postscript - Submitted Version
Download (1MB) | Preview
Download: [img] PDF - Submitted Version
Download (2MB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2006-518
Depositing User: Stefan Hachul
Date Deposited: 02 Mar 2006 00:00
Last Modified: 09 Apr 2014 13:09
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/518