[Yt-dev] treecode thoughts

[Matthew Turk]

Hi Stephen,

On Fri, Mar 25, 2011 at 2:44 PM, Stephen Skory <stephenskory at yahoo.com> wrote:
> 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.

Congratulations!  This is great.  Very nice work.

>
> 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.

That's interesting.  To be perfectly honest, I kind of expected it to
perform a bit better.  Any insight where the overhead comes from?

>
> 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?

It should be on by default.  What is the performance difference, for a
small/medium clump?  10%?  50%?  Factor of 10?

>
> 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.

No, don't bother with this.

>
> 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!

Very nice work!  I have reviewed your changes and I think you should
merge them.  This will be a shining addition to the 2.1 release.

Could you post a script verifying that it works for clumps on the edge
and in the center, to be added to the answer tests?

Best,

Matt

>
>
> Stephen Skory
> stephenskory at yahoo.com
> http://stephenskory.com/
> 510.621.3687 (google voice)
> _______________________________________________
> Yt-dev mailing list
> Yt-dev at lists.spacepope.org
> http://lists.spacepope.org/listinfo.cgi/yt-dev-spacepope.org
>