El problema de los n cuerpos y su paralelización

Abstract

Durante milenios, la humanidad ha tratado de predecir la posición de los astros que observaba en el cielo. Dado el gran número de cuerpos presentes en el espacio y su influencia gravitacional mutua, predecir sus movimientos involucra una gran cantidad de cómputo. Es tal su complejidad computacional que, durante el siglo XVII, este problema adquirió un nombre propio dentro del campo de la física: el problema de los n cuerpos. La naturaleza de este problema hace que el número de cálculos a realizar aumente muy rápidamente con el número de cuerpos tomados en consideración. Se han presentado soluciones analatícas para un número limitado de cuerpos. Sin embargo, para un número más grande de cuerpos, el problema solo presenta solución mediante simulación. Gracias a los computadores disponibles a día de hoy, es posible implementar una simulación del problema de los n cuerpos. No obstante, el método basado en fuerza bruta presenta una complejidad computacional de O(n2). En los años ochenta, Josh Barnes y Piet Hut presentaron un algoritmo basado en árbol que presentaba una complejidad de O(n log n). Además, este algoritmo presentaba la ventaja de ser paralelizable. El objetivo del presente trabajo de fin de grado consiste en implementar una simulación gráfica de los n cuerpos basada en cada uno de los tres métodos descritos: por fuerza bruta, basado en árbol secuencial y basado en árbol paralelo. Se presentan diferentes configuraciones de cuerpos y se obtendrán resultados para cada uno de ellos. Abstract: It's been thousands of years since mankind started to try to predict the position of the stars that they observed in the sky. However, given the great number of existing celestial bodies and their mutual gravitational in fluence, lots of computation is needed in order to predict their movements. Indeed, in the 17th century this computation became such a complex issue that it was even given a name in the field of physics: the n-body problem. Due to the nature of the problem, the number of calculations that have to be made increases in direct proportion to the number of celestial bodies taken into consideration. Analytical solutions have been presented for a limited number of bodies. However, when the number of bodies is too large, the only way to solve the problem is by simulation. Thanks to the computers available today, it is possible to implement a simulation of the n-body problem. However, the brute-force method has a computational complexity of O(n2). In the 1980s, Josh Barnes and Piet Hut introduced a treebased algorithm with a complexity of O(n log n). In addition, this algorithm had the advantage of being parallelizable. Therefore, this end-of-degree paper aims to implement a graphic simulation of the n-bodies based on each of the three existing methods: by brute force, based on a sequential tree and based on a parallel tree. Different configurations of bodies and their ensuing results will be presented.