Greengard's N-body algorithm is not order N

被引：17

作者：

Aluru, S

机构：

来源：

SIAM JOURNAL ON SCIENTIFIC COMPUTING | 1996年 / 17卷 / 03期

关键词：

Greengard's algorithm; N-body problem; particle simulation; tree algorithms for particle simulation;

D O I：

10.1137/S1064827593272031

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Greengard's N-body algorithm claims to compute the pairwise interactions ina system of N particles in O(N) time for a fixed precision. In this paper, we show that the choice of precision is not independent of N and has a lower bound of log N. We use this result to show that Greengard's algorithm is not O(N).

引用

页码：773 / 776

页数：4