Comparison of two different tree algorithms
Comparison of two different tree algorithms
复制标题
两种不同树算法的比较
DOI：
10.1016/0021-9991(90)90186-5
复制
发表时间：
1990
影响因子：
4.1
通讯作者：
J. Makino
中科院分区：
文献类型：
--
作者：
J. Makino
讨论了两种不同的分层力计算算法的效率。两种算法都利用树形结构来减少从mo （N2）到（NlogN）的力计算成本。唯一的区别在于树的构造方法。一种算法使用oct-tree，它是将一个立方体递归划分为八个子立方体。另一种方法是通过用一个超级粒子反复替换系统中最接近的一对来制作树。数值实验表明，在得到的力的相对精度相同的情况下，这两种格式的力计算成本相当。构造互近邻树的代价比构造八叉树的代价高大约10倍。在传统的大型机上，这种差异并不重要，因为树构造的成本只占总计算成本的一小部分。在向量处理器上，oct-tree方案目前更快，因为在向量处理器上构建树的成本相对更高。
The efficiency of two different algorithms of hierarchical force calculation is discussed. Both algorithms utilize the tree structure to reduce the cost of the force calculation fromO(N2) toO(NlogN). The only difference lies in the method of the construction of the tree. One algorithm uses the oct-tree, which is the recursive division of a cube into eight subcubes. The other method makes the tree by repeatedly replacing a mutually nearest pair in the system by a super-particle. Numerical experiments showed that the cost of the force calculation using these two schemes is quite similar for the same relative accuracy of the obtained force. The construction of the mutual-nearest-neighbor tree is more expensive than the construction of the oct-tree roughly by a factor of 10. On the conventional mainframes this difference is not important because the cost of the tree construction is only a small fraction of the total calculation cost. On vector processors, the oct-tree scheme is currently faster because the tree construction is relatively more expensive on the vector processors.