[Yt-svn] commit/yt-doc: sskory: Adding figures & discussion for the treecode.

[Bitbucket]

1 new changeset in yt-doc:

http://bitbucket.org/yt_analysis/yt-doc/changeset/54c3b8b26035/
changeset:   r61:54c3b8b26035
user:        sskory
date:        2011-04-06 19:05:11
summary:     Adding figures & discussion for the treecode.
affected #:  4 files (102.5 KB)

--- a/source/analysis_modules/clump_finding.rst	Tue Apr 05 22:26:24 2011 -0400
+++ b/source/analysis_modules/clump_finding.rst	Wed Apr 06 11:05:11 2011 -0600
@@ -40,10 +40,13 @@
 
   PE = \Sigma_{i=1}^N \Sigma_{j=i}^N \frac{G M_i M_j}{r_{ij}}
 
-where PE is the gravitational potential energy of N cells, G is the
-gravitational constant, M_i is the mass of cell i, and r_{ij} is the distance
-between cell i and j. The number of calculations required for this calculation
-grows with the square of N. Therefore, for large clumps with many cells, the
+where :math:`PE` is the gravitational potential energy of :math:`N` cells,
+:math:`G` is the
+gravitational constant, :math:`M_i` is the mass of cell :math:`i`, 
+and :math:`r_{ij}` is the distance
+between cell :math:`i` and :math:`j`.
+The number of calculations required for this calculation
+grows with the square of :math:`N`. Therefore, for large clumps with many cells, the
 test for boundedness can take a significant amount of time.
 
 An effective way to greatly speed up this calculation with minimal error
@@ -62,14 +65,14 @@
 ``opening_angle`` upon the remote mass. The default value is
 ``opening_angle = 1``, which gives errors well under 1%. A value of 
 ``opening_angle = 0`` is identical to the full O(N^2) method, and larger values
-will speed up the calculation and sacrifice accuracy.
+will speed up the calculation and sacrifice accuracy (see the figures below).
 
 The treecode method is iterative. Conglomerates may themselves form larger
 conglomerates. And if a larger conglomerate does not meet the ``opening_angle``
 criterion, the smaller conglomerates are tested as well. This iteration of 
 conglomerates will
 cease once the level of the original masses is reached (this is what happens
-if ``opening_angle = 0``).
+for all pair calculations if ``opening_angle = 0``).
 
 Below are some examples of how to control the usage of the treecode.
 
@@ -114,4 +117,70 @@
 To turn off the treecode, of course one should turn treecode=False in the
 example above.
 
+Treecode Speedup and Accuracy Figures
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
+Two datasets are used to make the three figures below. Each is a zoom-in
+simulation with high resolution in the middle with AMR, and then lower
+resolution static grids on the periphery. In this way they are very similar to
+a clump in a full-AMR simulation, where there are many AMR levels stacked
+around a density peak. One dataset has a total of 3 levels of AMR, and
+the other has 10 levels, but in other ways are very similar.
+
+The first figure shows the effect of varying the opening angle on the speed
+and accuracy of the treecode. The tests were performed using the L=10 
+dataset on a clump with approximately 118,000 cells. The speedup of up the
+treecode is in green, and the accuracy in blue, with the opening angle
+on the x-axis.
+
+With an ``opening_angle`` = 0, the accuracy is perfect, but the treecode is
+less than half as fast as the brute-force method. However, by an
+``opening_angle`` of 1, the treecode is now nearly twice as fast, with
+about 0.2% error. This trend continues to an ``opening_angle`` 8, where
+large opening angles have no effect due to geometry.
+
+.. image:: _images/TreecodeOpeningAngleBig.png
+   :width: 450
+   :height: 400
+
+Note that the accuracy is always below 1. The treecode will always underestimate
+the gravitational binding energy of a clump.
+
+In this next figure, the ``opening_angle`` is kept constant at 1, but the
+number of cells is varied on the L=3 dataset by slowly expanding a spherical
+region of analysis. Up to about 100,000 cells,
+the treecode is actually slower than the brute-force method. This is due to
+the fact that with fewer cells, smaller geometric distances,
+and a shallow AMR hierarchy, the treecode
+method has very little chance to be applied. The calculation is overall
+slower due to the overhead of the treecode method & startup costs. This
+explanation is further strengthened by the fact that the accuracy of the
+treecode method stay perfect for the first couple thousand cells, indicating
+that the treecode method is not being applied over that range.
+
+Once the number of cells gets high enough, and the size of the region becomes
+large enough, the treecode method can work its magic and the treecode method
+becomes advantageous.
+
+.. image:: _images/TreecodeCellsSmall.png
+   :width: 450
+   :height: 400
+
+The saving grace to the figure above is that for small clumps, a difference of
+50% in calculation time is on the order of a second or less, which is tiny
+compared to the minutes saved for the larger clumps where the speedup can
+be greater than 3.
+
+The final figure is identical to the one above, but for the L=10 dataset.
+Due to the higher number of AMR levels, which translates into more opportunities
+for the treecode method to be applied, the treecode becomes faster than the
+brute-force method at only about 30,000 cells. The accuracy shows a different
+behavior, with a dip and a rise, and overall lower accuracy. However, at all
+times the error is still well under 1%, and the time savings are significant.
+
+.. image:: _images/TreecodeCellsBig.png
+   :width: 450
+   :height: 400
+
+The figures above show that the treecode method is generally very advantageous,
+and that the error introduced is minimal.
\ No newline at end of file

Repository URL: https://bitbucket.org/yt_analysis/yt-doc/

--

This is a commit notification from bitbucket.org. You are receiving
this because you have the service enabled, addressing the recipient of
this email.