El problema de los n cuerpos y su paralelización

Blanco López, Alejandro (2019). El problema de los n cuerpos y su paralelización. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S.I. de Sistemas Informáticos (UPM), Madrid.

Description

Title: El problema de los n cuerpos y su paralelización
Author/s:
  • Blanco López, Alejandro
Contributor/s:
  • Carazo Minguela, Pablo
Item Type: Final Project
Degree: Grado en Ingeniería de Computadores
Date: July 2019
Subjects:
Freetext Keywords: Simulación gráfica
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img] PDF - Users in campus UPM only - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (686kB)
[img] Archive (ZIP) - Users in campus UPM only
Download (1MB)

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.

More information

Item ID: 56172
DC Identifier: http://oa.upm.es/56172/
OAI Identifier: oai:oa.upm.es:56172
Deposited by: Biblioteca Universitaria Campus Sur
Deposited on: 04 Sep 2019 05:42
Last Modified: 04 Sep 2019 05:42
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM