A hierarchical O(N log N) force-calculation algorithm

摘要: Until recently the gravitational N-body problem has been modelled numerically either by direct integration, in which computation needed increases as N2, or an iterative potential method number of operations grows N log N. Here we describe a novel directly calculating force on bodies that only The technique uses tree-structured hierarchical subdivision space into cubic cells, each is recursively divided eight subcells whenever more than one particle found to occupy same cell. This tree constructed anew at every time step, avoiding ambiguity and tangling. Advantages over potential-solving codes are: accurate local interactions; freedom from geometrical assumptions restrictions; applicability wide class systems, including (proto-)planetary, stellar, galactic cosmological ones. previous tree-codes include simplicity possibility rigorous analysis error. Although concentrate here stellar dynamical applications, our techniques efficiently handling large long-range interactions concentrating computational effort where most have applications other areas astrophysics well.