La simulación Barnes-Hut (llamada así 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 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 generalmente se divide 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 bajo orden ). Esto puede reducir drásticamente el número de interacciones de pares de partículas que deben calcularse.
Algunos de los proyectos informáticos 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 necesaria ]
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 secundarios.
Para calcular la fuerza neta sobre un cuerpo particular, se recorren los nodos del árbol, comenzando desde la raíz. Si el centro de masa de un nodo interno está suficientemente lejos del cuerpo, los cuerpos contenidos en esa parte del árbol se tratan como una sola partícula cuya posición y masa son 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á suficientemente lejos cuando esta relación es menor que un valor umbral θ . El parámetro θ determina la precisión de la simulación; valores más grandes 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 a un algoritmo de suma directa.
