Autor:	Fatih Erdogan Sevilgen, John L. Gustafson, G. M. Prabhu, Srinivas Aluru
Rok vydání:	1998
Předmět:	Mathematical optimization Computer science n-body problem Dimension (graph theory) Inverse-square law Motion (geometry) Upper and lower bounds Theoretical Computer Science Combinatorics Distribution (mathematics) Hardware and Architecture Quadtree Time complexity Software Information Systems
Zdroj:	The Journal of Supercomputing. 12:303-323
ISSN:	0920-8542
DOI:	10.1023/a:1008047806690
Popis:	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. Greengards 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 Greengards algorithm is distribution dependent and has a lower bound of (N log 2 N) in two dimensions and (N log 4 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 the N-body problem that runs in O(N log N) time for any fixed dimension.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::082d764e6386026331be870f7e023fbb https://doi.org/10.1023/a:1008047806690 Zobrazit plný text záznamu Full text from SpringerLink