Distribution-independent hierarchical N-body methods

<p>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; The problem has applications in several domains including astrophysics, molecular dynamics, fluid dynamics, radiosity methods in computer graphics and numerical complex analysis. Research efforts have focused on reducing the O(N[superscript]2) time per iteration required by the naive algorithm of computing each pairwise interaction. Widely respected among these are the Barnes-Hut and Greengard methods. Greengard claims his algorithm reduces the complexity to O(N) time per iteration;Throughout this thesis, we concentrate on rigorous, distribution-independent, worst-case analysis of the N-body methods. We show that Greengard's algorithm is not O(N), as claimed. Both Barnes-Hut and Greengard's methods depend on the same data structure, which we show is distribution-dependent. For the distribution that results in the smallest running time, we show that Greengard's algorithm is [omega](N log[superscript]2N) in two dimensions and [omega](N log[superscript]4N) in three dimensions. Both algorithms are unbounded for arbitrary distributions;We have designed a hierarchical data structure whose size depends entirely upon the number of particles and is independent of the distribution of the particles. We show that both Greengard's and Barnes-Hut algorithms can be used in conjunction with this data structure to reduce their complexity. Apart from reducing the complexity of the Barnes-Hut algorithm, the data structure also permits more accurate error estimation. We present two- and three-dimensional algorithms for creating the data structure. The multipole method designed using this data structure has a complexity of O(N log N) in two dimensions and O(N log[superscript]2 N) in three dimensions.</p>

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

dissertation

Department dc:contributor.department

Department of Computer Science

Year dc:date.issued

1994

Author dc:creator

• Aluru, Srinivas

Advisors dc:contributor.advisor

• G. M. Prabhu
• John Gustafson

Language dc:language.iso

en

DOI

https://doi.org/10.31274/rtd-180813-11599

Identifier

archive/lib.dr.iastate.edu/rtd/10673/

OAI identifier oai:identifier

oai:dr.lib.iastate.edu:20.500.12876/63845