Simulation de Barnes-Hut
La simulation de Barnes-Hut est un algorithme pour le problème à n corps dont la complexité en O(nln(n)) est remarquable, comparée à l'algorithme « naturel » qui est en O(n²). Elle porte le nom de Josh Barnes et Piet Hut.
Principe
L'idée est de découper l'espace en cubes (méthode de l'octree) en raffinant récursivement les tailles. On obtient ainsi un octree : un arbre dont la racine est l'espace complet considéré (lui-même un cube) et chaque nœud représente un cube de l'espace qui, ou bien contient une seule particule ou bien n'en contient pas, ou bien a 8 fils : les 8 huitièmes du cube précédent. Quand on cherche à calculer le mouvement d'une particule, pour les cubes dont le centre de gravité est éloigné, on ne considérera que leur centre de gravité, pour les autres on descendra dans l'arbre pour avoir un calcul plus précis. Remarquons que cela fait perdre en précision par rapport au calcul en force brute, mais permet d’accélérer sensiblement le calcul.