Simulation de Barnes-Hut

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Schéma des découpages successifs pendant la 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[modifier | modifier le code]

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.

Notes et références[modifier | modifier le code]

(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)