SKELETONS FROM THE TREE-CODE CLOSET

We consider treecodes (N-body programs which use a tree data structure ) from the standpoint of their worst-case behavior. That is, we derive upper bounds on the largest possible errors that are introduced into a calculation by use of various multipole acceptability criteria (MAC) . We find that the conventional Barnes-Hut MAC can introduce potential ly unbounded errors unless theta < 1/square-root 3, and that this beha vior while rare, is demonstrable in astrophysically reasonable example s. We consider two other MACs closely related to the BH MAC. While the y do not admit the same unbounded errors, they nevertheless require ex traordinary amounts of CPU time to guarantee modest levels of accuracy . We derive new error bounds based on some additional, easily computed moments of the mass distribution. These error bounds form the basis f or four new MACs which can be used to limit the absolute or relative e rror introduced by each multipole evaluation, or, with the introductio n of some additional data structures, the absolute or rms error in the final acceleration of each particle. Using the Sum Squares MAC to ana lytically place a 1 % bound on the rms error in a series of test model s, we find that it significantly outperforms the theta=0.65 BH MAC in terms of both accuracy (mean, rms, and maximum error) and performance (floating point operation count). (C) 1994 Academic Press, Inc.