Estudio e implementación del algoritmo Barnes-Hut para el cálculo de la interacción gravitatoria entre N-cuerpos

Abstract

[EN] In this work, we provide an original implementation of the Barnes-Hut algorithm in Python 3.7 both in 2D and 3D. This algorithm solves approximately the N-body problem and is well known for achieving order by treating nearby bodies as single individuals when observed from a far enough distance. Besides, we came up with a clever scheme for grouping those bodies: a proof of concept that turned out to perform accurately. Further, we analyzed the validity range of our prototype and correlated it to the direct-sum algorithm

by means of a selected set of test examples. Our implementation of the BH algorithm relies heavily on a deeply nested tree data structure. As such, its manipulation is fundamentelly recursive and highly complex. This is the reason why we additionally have included an extended explanation, with drawings and schemes, of the rather cumbersome bookkeeping strategy involved in its use. Finally, we have uploaded the full code to the GitHub platform and thereby made it publicly available.

[ES] Este trabajo proporciona una implementación original del algoritmo Barnes-Hut en Python 3.7, tanto en 2D como en 3D. Este algoritmo resuelve el problema de N-cuerpos de forma aproximada y es conocido por lograr el orden al agrupar los cuerpos cercanos en un solo individuo cuando son observados desde una distancia lo suficientemente lejana. Además, concebimos un esquema original para agrupar esos cuerpos; esta prueba de concepto resultó funcionar con precisión. Asimismo, analizamos el rango de validez de nuestro prototipo y lo contrastamos con el algoritmo de suma directa

mediante un conjunto seleccionado de ejemplos. Nuestra implementación del algoritmo BH depende en gran medida de una estructura de datos de tipo árbol profundamente anidada. Como tal, su manipulación es fundamentalmente recursiva y altamente compleja. Esta es la razón por la que hemos incluido una explicación extendida, con dibujos y esquemas, de la estrategia de contabilidad bastante engorrosa involucrada en su uso. Finalmente, hemos subido el código completo a la plataforma GitHub y, por lo tanto, lo hemos puesto a disposición del público.