A HIERARCHICAL O(N-LOG-N) FORCE-CALCULATION ALGORITHM
A HIERARCHICAL O(N-LOG-N) FORCE-CALCULATION ALGORITHM
复制标题
DOI：
10.1038/324446a0
复制
发表时间：
1986-12-04
期刊：
影响因子：
64.8
通讯作者：
HUT, P
中科院分区：
文献类型：
--
作者：
BARNES, J;HUT, P
直到最近，引力N体问题的数值模拟要么是通过直接积分，其中所需的计算量增加到N_2，要么是通过迭代位势方法，在迭代位势方法中，运算的数量增加到N_(LogN)。在这里，我们描述了一种直接计算无体上的力的新方法，该方法只增长为NlogN。该技术使用树形结构的空间分层细分为立方体单元，每当发现多个粒子占据同一单元时，每个立方体单元递归地划分为八个子单元。这棵树在每个时间步都会重新构建，避免了歧义和纠缠。与势解程序相比的优点是：精确的局部相互作用；不受几何假设和限制的自由；适用于广泛的系统，包括(原始)行星、恒星、银河和宇宙系统。与以前的分层树码相比，其优点包括简单性和对错误进行严格分析的可能性。虽然我们在这里专注于恒星动力学应用，但我们有效地处理大量远程相互作用并将计算工作集中在最需要的地方的技术在天体物理学的其他领域也有潜在的应用。
Until recently the gravitationalN-body problem has been modelled numerically either by direct integration, in which the computation needed increases asN2, or by an iterative potential method in which the number of operations grows asNlogN. Here we describe a novel method of directly calculating the force onNbodies that grows only asNlogN. The technique uses a tree-structured hierarchical subdivision of space into cubic cells, each of which is recursively divided into eight subcells whenever more than one particle is found to occupy the same cell. This tree is constructed anew at every time step, avoiding ambiguity and tangling. Advantages over potential-solving codes are: accurate local interactions; freedom from geometrical assumptions and restrictions; and applicability to a wide class of systems, including (proto-)planetary, stellar, galactic and cosmological ones. Advantages over previous hierarchical tree-codes include simplicity and the possibility of rigorous analysis of error. Although we concentrate here on stellar dynamical applications, our techniques of efficiently handling a large number of long-range interactions and concentrating computational effort where most needed have potential applications in other areas of astrophysics as well.