Distribution-independent hierarchical N-body methods

dc.contributor.advisor G. M. Prabhu
dc.contributor.advisor John Gustafson
dc.contributor.author Aluru, Srinivas
dc.contributor.department Computer Science
dc.date 2018-08-23T13:45:32.000
dc.date.accessioned 2020-06-30T07:06:42Z
dc.date.available 2020-06-30T07:06:42Z
dc.date.copyright Sat Jan 01 00:00:00 UTC 1994
dc.date.issued 1994
dc.description.abstract <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>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/rtd/10673/
dc.identifier.articleid 11672
dc.identifier.contextkey 6408804
dc.identifier.doi https://doi.org/10.31274/rtd-180813-11599
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath rtd/10673
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/63845
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/rtd/10673/r_9503526.pdf|||Fri Jan 14 18:25:44 UTC 2022
dc.subject.disciplines Computer Sciences
dc.subject.keywords Computer science
dc.title Distribution-independent hierarchical N-body methods
dc.type article
dc.type.genre dissertation
dspace.entity.type Publication
relation.isOrgUnitOfPublication f7be4eb9-d1d0-4081-859b-b15cee251456
thesis.degree.level dissertation
thesis.degree.name Doctor of Philosophy
Original bundle
Now showing 1 - 1 of 1
1.25 MB
Adobe Portable Document Format