Résolution du problème à n corps par l’algorithme de Barnes-Hut

Application

L’algorithme de Barnes-Hut est une méthode de résolution du problème à n corps en interaction (ici gravitationnelle) plus performante que la méthode consistant à calculer les n(n-1) interactions, lorsque n devient très grand. Elle s’applique à l’étude de ceintures d’astéroïdes, amas, disques d’accrétion…

Méthode

La méthode consiste à diviser l’espace en octree, dans lesquels sont répartis les corps. Le barycentre et la masse totale équivalente à chaque noeud d’un octree est calculée. Puis la force subie par chaque particule est calculée en sommant les forces exercées par chaque noeud dont la taille est suffisamment petite devant leur distance avec la particule considérée.

Progression actuelle

Suivre le dév. : http://github.com/lucasgautheron/barnes-hut

Pour l’instant j’ai posé les bases du code, et je pense une partie importante de la gestion de l’octree, et du calcul des interactions.

Vidéo du premier essai :

Voici un aperçu de l’octree correspondant à une distribution cylindrique de particules :

(Octree représentant une distribution cylindrique. 1000 corps.)

Octree représentant une distribution cylindrique. 1000 corps.

(Octree représentant une distribution "torique" (en anneau). 1000 corps.)

Octree représentant une distribution « torique » (en anneau). 1000 corps.

(Octree représentant une distribution sphérique de 1000 corps.)

Octree représentant une distribution sphérique de 1000 corps.

Complexité

La complexité de l’algorithme de Barnes-Hut est en \mathcal{O}(n.\ln n). En effet le calcul consiste à itérer d’un nombre \propto n \times k, où n est le nombre de corps et k la profondeur de l’octree. On peut montrer que la profondeur de l’octree est en ln n. Considérons que les n élements sont répartis dans un volume V et que chaque octant de profondeur maximale k doit contenir x éléments (En général on prend x = 1). On déterminer nk, le nombre d’éléments contenus dans un octant de profondeur k, en considérant la distribution spatiale de corps homogène :

 n_k = \dfrac{n}{V} . \dfrac{V}{8^k} = x

Soit :

\dfrac{n}{x} = 8^k \Leftrightarrow k = \dfrac{\ln \dfrac{n}{x}}{\ln 8}

Puisque x est très petit devant n, (et même souvent égal à 1), k = \mathcal{O}(\ln n), et on a bien un nombre d’itérations dominé par  n.\ln n

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *