[Yt-dev] treecode thoughts

[Stephen Skory]

Hi All,

Over the last two weeks I have been working on adding a treecode method as an option for calculating the gravitational boundedness of clumps. Now I can say that it's pretty much functional. I think there's at least one small optimization I can make before I am ready to merge & push it back into the mainline repo, but other than that I think things are pretty polished.

In summary, for medium to very large sized clumps (in terms of number of cells), the treecode is showing it's usefulness. My tests are not complete, but the break even line with the standard opening angle (==approximation control) of 1.0, is about 100,000 cells. For example, a spherical clump with three levels and 120,000 cells takes 272 seconds with the O(N^2) method, 175 seconds with the treecode, and has a 0.05% error.

One thought I have is whether or not the treecode should be a semi-automatic thing? As implied above, for small to medium clumps, the pure-C O(N^2) method is actually faster for several reasons. First, fewer data fields need to be generated. Second, small clumps will generally not benefit from the treecode method due to geometry, and the extra machinery of the octree slows it down, too. But for larger clumps, the treecode is clearly beneficial. The option to use the treecode would be a function of the number of cells in the clump. Thoughts?

As I've written things presently, the treecode will not help for unigrid datasets because the octree refinement levels match the dataset it's built to mirror. I think it should be possible to mock up fake levels in such a way that would allow the treecode method to work with unigrid datasets. In fact, I'm already doing something vaguely like this but only for the levels that actually exist in the dataset. My question is, do we think it is worth it? My impression is that clump finding is mostly done on AMR datasets, and this would add a bit of complexity. It's hard to say if it would have any advantage for AMR datasets.

I do need to do a bit of testing to make sure that my periodic changes work, but I don't foresee many problems with that.

I've already started adding some stuff to the docs on this, and I can finish them once the issues above are settled. Thanks for any thoughts you can share!

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