Algorithms

Around the same time, a few other algorithms were published that scaled either either as NlogN or as N. However, the simplicity of the basic structure of our tree code was considered to outweigh whatever formal advantages the other codes may have had, given the fact that our code soon became the standard work horse of grid-free N-body simulations.

A few years later, we published a detailed analysis of the scaling of the errors in an article Error Analysis of A Tree Code, by Barnes J.E. & Hut, P., 1989, Astrophys. J. Suppl. 70, 389-417, in which we analyzed extensions of the tree code to include high-order multipole moments in the characterization of the density distribution in each cell in the tree (from quadrupole and hexadecapole up to hexacontatetrapole).

In another project, we analyzed the relative importance of the algorithmic errors in the tree code and the `real-life' errors introduced by the fact that each simulation is an arbitrary stochastic representation of an ideal density distribution, in which the particle discreteness necessarily introduces its own errors. The result were publised as Discreteness Noise versus Force Errors in N-Body Simulations, by Hernquist, L., Hut, P. & Makino, J., 1993, Astrophys. J. 402, L85-88.   (Note the amusing erratum in Astrophys. J. 411, L53, in which we had to point out a superfluous `0' in the abstract, that had crept in while the paper was typeset: the first published version claimed that discreteness has intrinsic errors of 1000%....).

For a list of subsequent developments, such the analysis of Salmon and Warren who showed some interesting limitations to the choice of opening angle in simple versions of the tree code, see the literature list in Joshua Barnes' Treecode Guide.

To remedy this situation, we have developed an implicit algorithm in which we redefine the leapfrog for variable time steps in such a way that time reversal is maintained. In practice, the implicit scheme can often be solved in one or two iterative steps, with great gain in accuracy. The same treatment can be applied to the fourth-order generalization of the leapfrog, the Hermite scheme. Our results are described in the paper Building a Better Leapfrog, by Hut, P., Makino, J. & McMillan, S., 1995, Astrophys. J. Lett. 443, L93-L96.

Subsequent refinements were developed and published in the paper Time-Symmetrization of Kustaanheimo-Stiefel Regularization, by Funato, Y., Hut, P., McMillan, S. & Makino, J., 1996, Astron. J. 112, 1697-1708. Summaries of our techniques can be found in the conference proceeding articles Time-Symmetrized Kustaanheimo-Stiefel Regularization, by Funato, Y., Makino, J., Hut, P. & McMillan, S., 1996, in Dynamical Evolution of Star Clusters, I.A.U. Symp. 174, eds. P. Hut and J. Makino (Dordrecht: Kluwer), pp. 367-368, and Time Symmetrization Meta-Algorithms, by Hut, P., Funato, Y., Kokubo, E., Makino, J. & McMillan, S., 1997, in `Computational Astrophysics', the Proceedings of the 12th `Kingston meeting' on Theoretical Astrophysics, eds. D. A. Clarke and M. J. West, ASP Conference Series, Vol. 123 (San Francisco: ASP), pp. 26-31 (available in preprint form as astro-ph/9704276).

For the more complicated case of block time steps, there are several pitfalls that prevent a straightforward implementation. The first time symmetric treatment of block time steps was published as A New Time-Symmetric Block Time-Step Algorithm for N-Body Simulations, by Makino, J., Hut, P., Kaplan, M. & Saygin, H., J, 2006, New Astronomy xx, xxx-xxx (available in preprint form as astro-ph/0604371; in an earlier version by Kaplan, M., Saygin, H., Hut, P. & Makino, J, 2005, as astro-ph/0511304).

the HOP algorithm

Back to activities or to table of contents.

Back to Piet Hut's home page.