Simulación de Barnes – Hut

La simulación de Barnes-Hut (que lleva el nombre de Josh Barnes y Piet Hut ) es un algoritmo de aproximación para realizar una simulación de n cuerpos . Es notable por tener orden O ( n  log  n ) en comparación con un algoritmo de suma directa que sería O ( n 2 ). [1]

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

El volumen de simulación generalmente se divide en celdas cúbicas a través de un octárbol (en un espacio tridimensional), de modo que solo las partículas de las celdas cercanas deben tratarse individualmente, y las partículas en celdas distantes pueden tratarse como una sola partícula grande centrada en el centro de masa de la célula (o como una expansión multipolar de bajo orden ). Esto puede reducir drásticamente el número de interacciones de pares de partículas que deben calcularse.

Algunos de los proyectos de computación de alto rendimiento más exigentes realizan astrofísica computacional utilizando el algoritmo de código de árbol de Barnes-Hut, como DEGIMA . [2] [ cita requerida ]

El árbol de Barnes-Hut

En una simulación tridimensional de n cuerpos , el algoritmo de Barnes-Hut divide recursivamente los n cuerpos en grupos almacenándolos en un octárbol (o un árbol cuádruple en una simulación 2D). Cada nodo de este árbol representa una región del espacio tridimensional. El nodo superior representa todo el espacio y sus ocho hijos representan los ocho octantes del espacio. El espacio se subdivide de forma recursiva en octantes hasta que cada subdivisión contiene 0 o 1 cuerpos (algunas regiones no tienen cuerpos en todos sus octantes). Hay dos tipos de nodos en el octárbol: 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 cuerpos debajo de él y almacena el centro de masa y la masa total de todos sus cuerpos secundarios.

  • Distribución de partículas que se asemeja a dos galaxias vecinas.

  • Árbol completo de Barnes-Hut. (Los nodos que no contienen partículas no se dibujan)

  • Nodos del árbol de Barnes-Hut utilizados para calcular la fuerza que actúa sobre una partícula en el punto de origen.

  • n -Simulación corporal basada en el algoritmo de Barnes-Hut.

Calcular la fuerza que actúa sobre un cuerpo

Para calcular la fuerza neta sobre un cuerpo en particular, se atraviesan los nodos del árbol, comenzando desde la raíz. Si el centro de masa de un nodo interno está lo suficientemente lejos del cuerpo, los cuerpos contenidos en esa parte del árbol se tratan como una sola partícula cuya posición y masa es, respectivamente, el centro de masa y la masa total del nodo interno. Si el nodo interno está lo suficientemente cerca del cuerpo, el proceso se repite para cada uno de sus hijos.

Si un nodo está o no lo suficientemente lejos de un cuerpo, depende del cociente , donde s es el ancho de la región representada por el nodo interno, y d es la distancia entre el cuerpo y el centro de masa del nodo. El nodo está lo suficientemente lejos cuando esta relación es menor que un valor umbral θ . El parámetro θ determina la precisión de la simulación; los valores más altos de θ aumentan la velocidad de la simulación pero disminuyen su precisión. Si θ = 0, ningún nodo interno se trata como un solo cuerpo y el algoritmo degenera en un algoritmo de suma directa.

Referencias
  1. ^ Pfalzner, Susanne; Gibbon, Paul (1996). Métodos de árboles de muchos cuerpos en física . Cambridge [ua]: Universidad de Cambridge. Presione . págs.  2 , 3. ISBN 978-0-521-49564-6.
  2. ^ T. Hamada; et al. (2009). "Un novedoso algoritmo paralelo de recorridos múltiples para el código de árbol de Barnes-Hut en GPU, hacia una simulación de N-body rentable y de alto rendimiento". Comp. Sci. Res. Dev . 24 (1–2): 21–31. doi : 10.1007 / s00450-009-0089-1 . S2CID  31071570 .
Fuentes
  • J. Barnes y P. Hut (diciembre de 1986). "Un algoritmo jerárquico de cálculo de fuerza O ( N  log  N )". Naturaleza . 324 (4): 446–449. Código Bibliográfico : 1986Natur.324..446B . doi : 10.1038 / 324446a0 . S2CID  4267861 .
  • J. Dubinski (octubre de 1996). "Un código de árbol paralelo". Nueva Astronomía . 1 (2): 133-147. arXiv : astro-ph / 9603097v1 . Bibcode : 1996NewA .... 1..133D . doi : 10.1016 / S1384-1076 (96) 00009-7 . S2CID  119464486 .
  • U. Becciani; R. Ansalonib; V. Antonuccio-Delogua; G. Erbaccic; M. Gamberaa y A. Pagliarod (octubre de 1997). "Un código de árbol paralelo para la simulación de grandes cuerpos N : equilibrio dinámico de carga y distribución de datos en un sistema CRAY T3D". Comunicaciones de Física Informática . 106 (1-2): 105-113. arXiv : física / 9709003 . Código Bibliográfico : 1997CoPhC.106..105B . doi : 10.1016 / S0010-4655 (97) 00102-1 . S2CID  18428101 .
  • T. Ventimiglia y K. Wayne. "El algoritmo de Barnes-Hut" . Consultado el 30 de marzo de 2012 .

  • Treecodes, J. Barnes
  • Código de árbol paralelo
  • Ejemplo de HTML5 / JavaScript Simulación gráfica de Barnes-Hut
  • PEPC: el solucionador de Coulomb paralelo bastante eficiente , un código de árbol de Barnes-Hut paralelo de código abierto con kernel de interacción intercambiable para una multitud de aplicaciones
  • Programa paralelo de simulación de GPU N-body con recorrido rápido del árbol de partículas sin apilamiento
  • Simulador de galaxias de Barnes-Hut en beltoforion.de