Barnes-Hut Algorithm

Barnes-Hut Algorithm

Divide and Conquer Algorithms are very popular for solving problems in an efficient means as well as for its pure simplicity. The algorithm in discussion is the Barnes-Hut algorithm, which is also a Divide and Conquer algorithm. The Barnes-Hut algorithm has a computational complexity of O(n log n), which is not super speedy, but tends to out perform even O(n) algorithms, especially direct summation types. The reason being, is that the (Grama, Kumar, Sameh, June 6, 2003) associated constants are smaller, particularly for simulations in three dimensions. Simply put, (~gurari, June 6, 2003) divide and conquer algorithms split large tasks into small pieces, and from there applies its algorithm onto the small pieces; continually. When the solutions to the small piece tasks are conceived, those small solutions are merged together to accomplish the large task.

The Barnes-Hut algorithm is an algorithm developed in the "divide and conquer" realm. The algorithm was (Dr. John Wallin, June 6, 2003) originated in 1986 by Josh Barnes and Piet Hut. The main use of the Barnes-Hut algorithm is calculating the distances apart that subjective particles are of a large assembly of particles. (Dr. John Wallin, June 6, 2003) And the reasoning behind this is to enable the proficient computation of forces so that the dynamic evolution of the system can be predicted. The specific of this algorithm is to make the problem space a rectangular parallel piped whose sides are of equal length.

The deeper explanation for Barnes-Hut algorithm works as follows. There are two phases, the tree construction phase and the force computation phase. (Grama, Kumar, Sameh, June 6, 2003) For the tree construction phase, a spatial tree representation of the domain (tree) is derived. In this phase, if the tree contains more than one particle, it is recursively divided into four equal parts for a two dimensional layout (2² * dimensional). This process will continue until each part has a single element in it, or also possible no particles in it. (Grama, Kumar, Sameh, June 6, 2003) For each array, or part of particles, they will be placed and constructed into a quad-like tree (2² * dimensional), which is now traversed in the post-order transversal arrangement. And for each node of the new quad-like tree a representation of those particles are contained in that tree.

The Barnes-Hut algorithm seems to be a rather popular algorithm, or at least to the scientific community. Its uses are probably for specific needs in the individual area; which may include navigational, military, and physics analysis.

Bibliography