[yt-users] A treecode for the clump finder

[Stephen Skory]

Hi All,

I have just pushed to the development branch of yt a modification to the clump finder(*) which should make the identification of gravitationally bound clumps run much more quickly. Previously, the gravitational potential energy of clumps was calculated using the full double sum that iterates over all unique pairs of cells in the clump. This is, of course, accurate, but it is quite slow because it is an O(N^2) operation.

A generally much faster and very accurate (but not perfectly accurate) method of calculating gravitational potentials is the treecode method of Barnes & Hut [1] which reduces the operation down to O(N log N). Using the Octree that Matt added to yt some time ago (and had never used) I implemented a treecode on top of it. There may be some further optimizations to the code, but especially for clumps larger than 100,000 cells, the treecode is substantially faster, up to several times for very large clumps. For intermediate clumps of a few tens of thousands of cells, the treecode is actually a bit slower, but no worse than 50%. This is due to likely both the extra cost of setting up the treecode hierarchy, and perhaps some optimizations I have yet to catch. At any rate, for now the time gains from the very large clumps should offset the time losses for smaller clumps.

Unfortunately, the treecode will not help unigrid datasets because the levels of the octree mirror the levels in the dataset, and a treecode needs more than one level to work. But it is my impression that people do not do clump finding on unigrid datasets. Please correct me if my impression is wrong! Also, the octree is x2 refinement-specific.

In the course of this work I noticed that periodic clumps would not be processed correctly, so I have added some machinery that should fix that using either the N^2 or treecode method.

The treecode is now on by default in the development branch. Let me know if you have any questions, or problems with the code. Thanks!

[1] http://adsabs.harvard.edu/abs/1986Natur.324..446B

(*) To be precise, the modifications are to the "IsBound" derived quantity, but that is most often called from within the clump finder. As a point of fact, I have actually not touched the clump finder at all.

 
Stephen Skory
stephenskory at yahoo.com
http://stephenskory.com/
510.621.3687 (google voice)