Error analysis of a tree code

Abstract

Novel algorithms called 'tree codes' are used to solve the gravitational N-body problem with computing time of order N log N or N instead of N-squared. A detailed analytic and numerical investigation of the error properties and performance of one such tree code, which is based on a hierarchical partition of space into cubical cells, is presented. The effect of replacing a distant cell containing many particles with a single point mass is considered, and it is found that the scaling of errors with opening angle and particle number can be well understood theoretically. The net effect of many such errors on the total force on a single particle within a large-N system is considered, and the cumulative effect of force- calculation errors on the trajectories of individual particles and the dynamical evolution of N-body systems is addressed. It is concluded that as a general class, tree codes appear to be the method of choice when modeling collisionless three-dimensional N-body systems with arbitrary geometry.