Date: Tue, 10 Dec 1996 22:04:37 GMT Server: NCSA/1.4.2 Content-type: text/html Last-modified: Mon, 29 Jul 1996 17:15:45 GMT Content-length: 1515 Experimental Analysis of Treecodes

Experimental Analysis of Treecodes for Astronomical Simulations


The introduction of hierarchical tree data-structures to solve the N-body problem have led to a host of algorithms with asymptotic complexities ranging from O(n log n) to O(n). Although the asymptotic complexity of different treecodes are competitive, the constant factors between the algorithms have a significant impact on the CPU time. In this paper we examine the performance of a class of treecodes to compare the effectiveness of different tree structures for N-body simulation. We investigate the performance of these treecodes in both the serial and parallel cases.


This work is in connection with a project on data structures by Prof. Richard Anderson. A draft paper is also available.

I have also put together a simple applet that animates an N-body simulation.


Sean David Sandys <sds@cs.washington.e du>

Last revised: April 4, 1995