Dual Hierarchy for Gravitational n-body
J.R. Campolattaro (TU Delft - Electrical Engineering, Mathematics and Computer Science)
E. Eisemann – Graduation committee member (TU Delft - Computer Graphics and Visualisation)
K. Hildebrandt – Mentor (TU Delft - Computer Graphics and Visualisation)
Mottaqiallah Taouil – Graduation committee member (TU Delft - Computer Engineering)
More Info
expand_more
Git repository containing an implementation of the adapted Dual Hierarchy algorithm for Gravitational n-body, as well as implementations of several other common algorithms compared against during benchmarking.
https://github.com/JacksonCampolattaro/n-bodyOther than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The n-body problem is the simulation of pair-wise interactions between n objects. This problem appears in many forms, with the classic example being the modeling of gravitational forces between point masses, necessary for cosmological simulations. Many approximation approaches have been devised to reduce the complexity of this problem.
t-SNE is a data visualization method that requires repeatedly solving a variant of the n-body problem. A recent paper (An Efficient Dual-Hierarchy t-SNE Minimization, van de Ruit et. al.) proposes a novel algorithm that outperforms other t-SNE minimization methods on medium-scale datasets. The report proves the viability of a dual-traversal method that uses an embedding tree to emit forces and an independent field tree to collect forces. Because the embedding tree is a Linear-BVH and the field tree is an orthtree built to a fixed depth, the overall algorithm has linear complexity.
This thesis demonstrates how the dual-tree approach can be adapted for gravitational n-body simulations. Following this, it measures the performance against similar implementations of other algorithms and shows that while the adapted Dual Hierarchy approach is faster than Barnes-Hut, it is outperformed by the Fast Multipole Method on realistic large-scale cosmological datasets.