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.
","abstract_html":"<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>","abstract_has_math":false,"creators":["Aluru, Srinivas"],"institution":null,"degree_name":"Doctor of Philosophy","degree_level":"dissertation","degree_discipline":null,"degree_department":"Department of Computer Science","school":null,"contributors":[],"advisors":["G. M. Prabhu","John Gustafson"],"committee_chairs":[],"committee_members":[],"year":1994,"date_issued":"1994","date_published":"1994","updated_at":"2026-07-24T02:39:41Z","subjects":[],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.31274/rtd-180813-11599"],"render_values":[{"text":"https://doi.org/10.31274/rtd-180813-11599","href":"https://doi.org/10.31274/rtd-180813-11599","code":true}]},{"key":"dc:identifier","label":"Identifier","values":["archive/lib.dr.iastate.edu/rtd/10673/"],"render_values":[{"text":"archive/lib.dr.iastate.edu/rtd/10673/","href":null,"code":true}]}]},"links":{"outbound_url":"https://dr.lib.iastate.edu/handle/20.500.12876/63845","outbound_label":"Repository record","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["G. M. Prabhu","John Gustafson"]},{"key":"dc:contributor.department","label":"Department","values":["Department of Computer Science"]},{"key":"dc:creator","label":"Author","values":["Aluru, Srinivas"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-08-23T13:45:32.000"]},{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2020-06-30T07:06:42Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2020-06-30T07:06:42Z"]},{"key":"dc:date.issued","label":"Date","values":["1994"]},{"key":"dc:type","label":"Dc Type","values":["dissertation"]},{"key":"thesis:degree_level","label":"Degree Level","values":["dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["archive/lib.dr.iastate.edu/rtd/10673/"]},{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.31274/rtd-180813-11599"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://dr.lib.iastate.edu/handle/20.500.12876/63845"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Distribution-independent hierarchical N-body methods"]}]}],"canonical_facts":{"dc:contributor.advisor":["G. M. Prabhu","John Gustafson"],"dc:contributor.department":["Department of Computer Science"],"dc:creator":["Aluru, Srinivas"],"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.issued":["1994"],"dc:description.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; 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.
"],"dc:format.mimetype":["application/pdf"],"dc:identifier":["archive/lib.dr.iastate.edu/rtd/10673/"],"dc:identifier.doi":["https://doi.org/10.31274/rtd-180813-11599"],"dc:identifier.uri":["https://dr.lib.iastate.edu/handle/20.500.12876/63845"],"dc:language.iso":["en"],"dc:title":["Distribution-independent hierarchical N-body methods"],"dc:type":["dissertation"],"thesis:degree_level":["dissertation"],"thesis:degree_name":["Doctor of Philosophy"]},"updated_at":"2026-07-24T02:39:41Z"}