A FAST ALGORITHM FOR PARTICLE SIMULATIONS
A FAST ALGORITHM FOR PARTICLE SIMULATIONS
复制标题
DOI：
10.1016/0021-9991(87)90140-9
复制
发表时间：
1987-12-01
影响因子：
4.1
通讯作者：
ROKHLIN, V
中科院分区：
文献类型：
--
作者：
GREENGARD, L;ROKHLIN, V
提出了一种算法，用于快速计算包含大量粒子的系统中的势场和力场，这些粒子的相互作用本质上是库仑或引力的。对于N粒子系统，传统上需要O(N2)量级的功来计算所有成对相互作用，除非使用某种近似或截断方法。本文的算法需要与N成正比的工作量来计算所有相互作用，使其在舍入误差范围内，使其更适用于等离子体物理、流体动力学、分子动力学和天体力学中遇到的大规模问题。
An algorithm is presented for the rapid evaluation of the potential and force fields in systems involving large numbers of particles whose interactions are Coulombic or gravitational in nature. For a system ofNparticles, an amount of work of the orderO(N2) has traditionally been required to evaluate all pairwise interactions, unless some approximation or truncation method is used. The algorithm of the present paper requires an amount of work proportional to N to evaluate all interactions to within roundoff error, making it considerably more practical for large-scale problems encountered in plasma physics, fluid dynamics, molecular dynamics, and celestial mechanics.