A Provably Fast Multipole Method
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.
Download: |
Download (1MB) | Preview |
---|---|
Download: |
Download (2MB) | Preview |
Editorial actions: | ![]() |
Item Type: | Paper (Technical Report) |
---|---|
Citations: | No citation data. |
Uncontrolled Keywords: | N-body simulations tree codes fast multipole method quadtree |
Subjects: |
|
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger |
Related URLs: |
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 |