Re: Barnes-Hut treecode (was Re: Galaxy Interaction Simulations)

Shawn Slavin (sdslavin@pegasus2.astro.indiana.edu)
Wed, 9 Mar 1994 03:15:22 GMT

In article <2lileh$qn9@elroy.jpl.nasa.gov>,
Andy Boden <andy@henry.jpl.nasa.gov> wrote:
>In article <2lh1k8INNj9c@watt.cs.unc.edu>, leech@cs.unc.edu (Jon Leech) writes:
>> In article <2l54nt$rkp@darkstar.UCSC.EDU> hos@helios.UCSC.EDU (Chris Mihos) writes:
>> >A treecode is an Nbody code which sorts the particles into nested
>> >hierarchical structures (hence the "tree" label) and evaluates the
>> >force between each particle and either other particles or hierarchical
>> >groups of particles, depending on accuracy criteria. It has the advantage
>> >of the CPU time scaling as NlogN rather than N^2 as direct nbody routines do.
>>
>> I think it's more accurate to say it's bounded by O(N log N) and O(N^2)
>> (if not worse), since asymptotic performance depends on the accuracy
>> criterion.
>>
>> Jon
>> __@/
>
>First let me say that I think this characterization of Jon's is
>correct -- based on my (as of yet) limited readings in literature.
>There are pathologies in these these algorithms that will result in
>N^2 time complexity -- similar to the pathologies in heapsort (see
>Knuth or NumRecipes). Chris' characterization is probably more useful
>for the novice (like me) reading "when used *correctly*, these codes
>give NlogN scaling".

[Stuff deleted.]

I'm not an expert (you've heard that a few times, eh?), but my understanding is
that the best case goes as N*ln(N), and worst case the thing degenerates to
full blown N-body code running at N**2 performance.

Also, I think it depends an what you're running, but a 10^4 particle simulation
could take a while on a Sparc. I'll have to talk to a fellow grad student to
get the specifics, but there's a treecode used here to simulate compact galaxy
clusters (~5 galaxies) which can take several days to get a merger or
non-merging result. I'll have to find out more, as this is not an appropriate
answer.

A point of interest: Treecodes can be highly efficient when vectorized and run
on a parallel machine. I am told that one of the above cD cluster simulations
which takes ~week on an HP735 has been run on IU's new Intel Paragon MPP
machine (64 nodes), taking 9 hours.

> 3) How do folks visualize the output of these simulations (I'm
>X-windows based, so I guess the question should be read with this in
>mind). In this case I think I can solve this problem with tools I
>already know about. But again it's stupid to screw around with
>something that's not quite right if the "right tool for the job" is
>sitting out there somewhere on an ftp site.

Another grad student here has been working on visualization of these cluster
simulations. The product used is called AVS (X11 based), and through the use
of scripts, NFS mounting of an enormous amount of disk space and much patience,
video movies of these simulations are made with support from IU's CICA (Center
for Innovative Computing Applications). Keep your eyes open, as you may see
these in the near future. Also, for a preview of an MPEG of one of these
simulations, check out http://enif.astro.indiana.edu, the IU Astro WWW server.

-- 
Shawn Slavin
Indiana University Astronomy


Internet:  sdslavin@pegasus2.astro.indiana.edu