Barnes-Hut simulation

Barnes-Hut simulation

The Barnes-Hut simulation is an algorithm for performing an N-body simulation. It is notable for having order O(n log n) compared to a direct-sum algorithm which would be O(n2).

The simulation volume is usually divided up into cubic cells via an octree, so that only particles from nearby cells need to be treated individually, and particles in distant cells can be treated as a single large particle centered at its center of mass (or as a low-order multipole expansion). This can dramatically reduce the number of particle pair interactions that must be computed. To prevent the simulation from becoming swamped by computing particle-particle interactions, the cells must be refined to smaller cells in denser parts of the simulation which contain many particles per cell.

References

*J. Barnes and P. Hut. A hierarchical O(N log N) force-calculation algorithm. Nature, 324(4), December 1986.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Barnes-Hut-Algorithmus — Der Barnes Hut Algorithmus ist ein 1986 von Josh Barnes und Piet Hut veröffentlichtes Näherungsverfahren, das eine effektive Berechnung der Kräfte in einem N Körperproblem ermöglicht. Im Gegensatz zur direkten Aufsummierung der Kräfte, deren… …   Deutsch Wikipedia

  • Hut — may refer to:*Hut (dwelling) ** Mountain hut *Hans Hut (1490 1527), an Anabaptist leader *Hut Records, a British audio records company *Sunglass Hut International, largest American retailer of sunglasses *Software Hut, a computer software… …   Wikipedia

  • Barnes — may refer to:In people: * Barnes (name), a family name and a given name, (includes lists of people with that name)In places: * Barnes, New South Wales, Australia * Barnes, London, UK. ** Barnes railway station * Barnes, Kansas, U.S. * Barnes… …   Wikipedia

  • N-body simulation — This article is about a topic in physics. For the automobile platform, see GM N platform. The Millennium Run simulates the universe until the present state, where structures are abundant, manifesting themselves as stars, galaxies and clusters An… …   Wikipedia

  • Discrete element method — A discrete element method (DEM), also called a distinct element method is any of family of numerical methods for computing the motion of a large number of particles of micrometre scale size and above. Though DEM is very closely related to… …   Wikipedia

  • Parallel computing — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computing …   Wikipedia

  • Force-based algorithms — Force based or force directed algorithms are a class of algorithms for drawing graphs in an aesthetically pleasing way. Their purpose is to position the nodes of a graph in two dimensional or three dimensional space so that all the edges are of… …   Wikipedia

  • Multipole moment — In mathematics, especially as applied to physics, multipole moments are the coefficients of a series expansion of a potential due to continuous or discrete sources (e.g., an electric charge distribution). A multipole moment usually involves… …   Wikipedia

  • Discrete element method — Mit Discrete Element Method (DEM) wird eine 1979 von Cundall und Strack entwickelte numerische Berechnungsmethode bezeichnet, mit der die Bewegung einer großen Zahl von Teilchen berechnet werden kann. Die Methode wird manchmal auch als Distinct… …   Deutsch Wikipedia

  • Diskrete-Elemente-Methode — Mit Discrete Element Method (DEM) wird eine 1979 von Cundall und Strack entwickelte numerische Berechnungsmethode bezeichnet, mit der die Bewegung einer großen Zahl von Teilchen berechnet werden kann. Die Methode wird manchmal auch als Distinct… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”