Simulación Barnes-Hut

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

La simulación Barnes-Hut ( Josh Barnes y Piet Hut ) es un algoritmo para realizar una simulación de n-cuerpos. Se destaca por tener un orden O(n log n) en comparación con un algoritmo de suma directa que sería O(n2).

Una simulación 100-cuerpo con el árbol de Barnes-Hut visualmente como cajas azules.

El volumen de la simulación está generalmente dividido en células cúbicas a través de un octree (en un espacio tridimensional), de manera que sólo las partículas de las células cercanas necesitan ser tratadas individualmente, y las partículas en células distantes puede ser tratadas como una sola partícula grande centrada en el centro de la célula (o como de orden inferior desarrollo multipolar ). Esto puede reducir drásticamente el número de interacciones pares de partículas que deben ser calculadas.

Algoritmo[editar]

Árbol Barnes-Hut[editar]

En una simulación de n-cuerpos bidimensional, el algoritmo Barnes-Hut divide recursivamente los n cuerpos en grupos, almacenándolos en un Quadtree. Cada nodo en este árbol representa una región del espacio de dos dimensiones. El nodo superior representa todo el espacio, y sus cuatro niños representan los cuatro cuadrantes del espacio y cada cuadrante de nuevo se pueden dividir en cuatro cuadrantes. El espacio se divide en cuadrantes de forma recursiva hasta que cada subdivisión contiene a 0 o 1 cuerpos (algunas regiones no tienen cuerpos en todos sus cuadrantes). Hay dos tipos de nodos en el árbol cuádruple: nodos internos y externos. Un nodo externo no tiene hijos, y está vacío o representa un solo cuerpo. Cada nodo interno representa el grupo de organismos que dependen de ella, y almacena el centro de la masa y la masa total de todos sus órganos de niños.

Cálculo de la fuerza que actúa sobre un cuerpo[editar]

Para calcular la fuerza neta sobre un cuerpo en particular, los nodos del árbol son atravesadas, a partir de la raíz. Si el centro de masa de un nodo interno está suficientemente lejos del cuerpo, los órganos contenidos en esa parte del árbol se tratan como un solo cuerpo, cuya posición y la masa es, respectivamente, del centro de masa y la masa total del nodo interno. Si el nodo interno no es lo suficientemente lejos del cuerpo, el proceso se repite para cada uno de sus hijos.

Si un nodo es o no es lo suficientemente lejos de un cuerpo, depende del cociente s / d, donde s es la anchura de la región representada por el nodo interno, y d es la distancia entre el cuerpo y el centro del nodo de masa. El nodo es suficientemente lejos cuando esta relación es menor que un valor umbral θ. El θ parámetro determina la exactitud de la simulación, los valores más grandes de θ aumentar la velocidad de la simulación, pero disminuye su exactitud. Si θ = 0, no hay ningún nodo interno es tratado como un solo cuerpo y el algoritmo degenera a un algoritmo de suma directa.

Referencias[editar]

  • J. Barnes and P. Hut (December 1986). «A hierarchical O(N log N) force-calculation algorithm». Nature 324 (4):  pp. 446–449. doi:10.1038/324446a0. 
  • J. Dubinski (October 1996). «A Parallel Tree Code». New Astronomy 1 (2):  pp. 133–147. doi:10.1016/S1384-1076(96)00009-7. arΧiv:astro-ph/9603097v1. 
  • U. Becciani, R. Ansalonib, V. Antonuccio-Delogua, G. Erbaccic, M. Gamberaa, and A. Pagliarod (October 1997). «A parallel tree code for large N-body simulation: dynamic load balance and data distribution on a CRAY T3D system». Computer Physics Communications 106 (1–2):  pp. 105–113. doi:10.1016/S0010-4655(97)00102-1. 
  • T. Ventimiglia, and K. Wayne. «The Barnes-Hut Algorithm». Consultado el 30 de marzo de 2012.