DocumentCode :
2280153
Title :
Truly distribution-independent algorithms for the N-body problem
Author :
Aluru, Srinivas ; Prabhu, G.M. ; Gustafson, John
Author_Institution :
Ames Lab., Iowa State Univ., Ames, IA, USA
fYear :
1994
fDate :
14-18 Nov 1994
Firstpage :
420
Lastpage :
428
Abstract :
The N-body problem is to simulate the motion of N particles under the influence of mutual force fields based on an inverse square law. Greengard´s algorithm claims to compute the cumulative force on each particle in O(N) time for a fixed precision irrespective of the distribution of the particles. In this paper, we show that Greengard´s algorithm is distribution dependent and has a lower bound of Ω(N log2 N) in two dimensions and Ω(N log4 N) in three dimensions. We analyze the Greengard and Barnes-Hut algorithms and show that they are unbounded for arbitrary distributions. We also present a truly distribution independent algorithm for solving the N-body problem in O(N log N) time in two dimensions and in O(N log2 N) time in three dimensions
Keywords :
N-body problems; computational complexity; data structures; physics computing; Greengard´s algorithm; N particle motion simulation; N-body problem; arbitrary distributions; cumulative force; distribution dependent; distribution independent algorithm; distribution-independent algorithms; inverse square law; lower bound; mutual force fields; problem solving; Clustering algorithms; Computational modeling; Computer science; Data structures; Distributed computing; Electrostatics; Fluid dynamics; Force; Laboratories; Plasma applications;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Supercomputing '94., Proceedings
Conference_Location :
Washington, DC
Print_ISBN :
0-8186-6605-6
Type :
conf
DOI :
10.1109/SUPERC.1994.344305
Filename :
344305
Link To Document :
بازگشت