Gravitaatiosimulaatiot - Peiponen, Aapo (2019)
Tässä tutkielmassa tarkastellaan gravitaatiosimulaatioita, simulaatioiden tehokkuutta ja algoritmeja, joilla simulaatioita voidaan nopeuttaa. Gravitaatiosimulaatioiden suurin ongelma on laskennallinen vaativuus. Suoraan N kappaleen välisiä vuorovaikutuksia laskemalla laskennallinen vaativuus on luokkaa O(N^2). On selvää, että tämä on ongelma suurilla kappalemäärillä. Erilaiset algoritmit, kuten Barnes-Hut puualgoritmi, voivat vähentää aikavaativuutta tuntuvasti. Parhaimmillaan voidaan saavuttaa nopealla moninapamenetelmällä aikavaativuus O(N). Simulaatioita voidaan lisäksi nopeuttaa hyödyntämällä rinnakkaislaskentaa. Tähän soveltuu esimerkiksi Barnes–Hut-algoritmi hyvin.