An efficient CUDA implementation of the tree-based Barnes hut n-body algorithm

Abstract

The Barnes Hut force-calculation algorithm [1] is widely used in n-body simulations such as modeling the motion of galaxies. It hierarchically decomposes the space around the bodies into successively smaller boxes, called cells, and computes summary information for the bodies contained in each cell, allowing the algorithm to quickly approximate the forces (e.g., gravitational, electric, or magnetic) that the n bodies induce upon each other. The hierarchical decomposition is recorded in an octree, which is the three-dimensional equivalent of a binary tree. With n bodies, the precise force calculation needs to evaluate O(n2) interactions. The Barnes Hut algorithm reduces this complexity to O (n log n) and thus makes interesting problem sizes computationally tractable. When you are citing the document, use the following link http://essuir.sumdu.edu.ua/handle/123456789/34839