La simulación de Barnes-Hut (nombrada en honor a Josh Barnes y Piet Hut ) es un algoritmo de aproximación 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( n 2 ). [1]
El volumen de simulación se divide generalmente en celdas cúbicas a través de un octree (en un espacio tridimensional), de modo que solo las partículas de las celdas cercanas deben tratarse individualmente, y las partículas de las celdas distantes pueden tratarse como una sola partícula grande centrada en el centro de masa de la celda (o como una expansión multipolar de orden bajo ). Esto puede reducir drásticamente la cantidad 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 ]
En una simulación tridimensional de N cuerpos , el algoritmo de Barnes-Hut divide recursivamente los n cuerpos en grupos almacenándolos en un octree (o un quad-tree 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 recursivamente 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 octree: 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 hijos.
Para calcular la fuerza neta sobre un cuerpo en particular, se recorren los nodos del árbol, comenzando desde la raíz. Si el centro de masas de un nodo interno está suficientemente alejado del cuerpo, los cuerpos contenidos en esa parte del árbol se tratan como una única partícula cuya posición y masa son respectivamente el centro de masas y la masa total del nodo interno. Si el nodo interno está suficientemente cerca del cuerpo, el proceso se repite para cada uno de sus hijos.
Si un nodo está o no suficientemente alejado 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á suficientemente alejado cuando esta relación es menor que un valor umbral θ . El parámetro θ determina la precisión de la simulación; valores mayores 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.
