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.

Schéma des découpages successifs pendant la simulation de Barnes-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.

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

Liens externes
  • Portail de l'informatique théorique
  • Portail de la physique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.