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(n ln(n)) est remarquable, comparée à l'algorithme « naturel » qui est en O(n2). 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
Recherche des plus proches voisins
Notes et références
Liens externes
- Le cours James Demmel à Berkeley
- Portail de l'informatique théorique
- Portail de la physique