Simulation de Barnes-Hut

Cet article est une ébauche concernant l’informatique et la physique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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.

Voir aussi

Méthode multipolaire rapide

Recherche des plus proches voisins

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Barnes–Hut simulation » (voir la liste des auteurs).