Le “problème à N corps” consiste à déterminer le mouvement de N masses sous l’effet des forces d’attraction gravitationnelles entre elles.
Pour N=3, Poincaré avait découvert que les trajectoires des corps pouvaient être “chaotiques” : une toute petite différence dans les positions et vitesses initiales des corps pouvait causer de très importantes différences dans la trajectoire des corps. Cependant, malgré ce que beaucoup croient, il existe une solution analytique au problème des trois corps découverte en 1909 par Karl Sundman. Elle n’est cependant pas utilisable en pratique pour des calculs.
Pour plus de 3 corps, il n’existe pas de solution analytique. Ceci signifie entre autres qu’il n’est pas possible de démontrer la stabilité d’un système avec quelques corps, comme le Système Solaire par exemple. Des mathématiciens comme Laplace ou Lyapunov s’y sont cassés les dents : rien ne prouve que les planètes suivront toujours leurs orbites actuelles dans quelques centaines de millions d’années. Encore moins qu’un astéroïde viennent percuter notre belle planète beaucoup plus tôt.
Simulation du Système Solaire sur Univers Sandbox, N~20
Il est aujourd’hui facile de simuler quelques millions d’années d’évolution du Système Solaire sur un PC, par exemple avec Universe Sandbox, le chouette programme dont j’ai déjà parlé ici. Comme on connait avec une très grande précision la position, la vitesse et la masse des planètes et de leurs principaux satellites, on estime que l’on peut calculer leur position dans 5 millions d’années à 150m près. Pour arriver à cette précision, mais aussi tout simplement pour réaliser une simulation réaliste, il faut tout particulièrement veiller à la l’intégration numérique utilisée, pour garantir la conservation de l’énergie totale du système. Selon cette étude, la méthode de Gauss-Hermite donne les meilleurs résultats.
D’autre part, pour chacun des N corps, il faut calculer les N-1 forces exercées par les autres corps. Au total, il faudra calculer [N.(N-1)]/2 forces (le /2 vient du fait qu’il suffit de ne calculer qu’une fois la force entre deux corps). On dit que la complexité est O(N²) : il faut effectuer un nombre d’opérations proportionnel au carré de N. Pour quelques dizaines de corps, ça ne pose aucun problème, mais si l’on veut simuler des galaxies ou même la collision de galaxies avec N=1′000′000, on se retrouve avec mille milliards de forces à évaluer, ce qui nécessite beaucoup de temps de calcul.
Simulation de la future collision de la Voie Lactée et d'Andromède, N=100'000'000
On pourrait se dire qu’une petite étoile à un bout de la galaxie n’attire pratiquement pas une autre petite étoile très distante, mais négliger cette force n’est pas une bonne idée. D’une part, l’énergie totale du système ne serait plus conservée, et d’autre part il faudrait trouver un critère permettant de savoir quelles forces sont négligeables, sans les calculer.
Barnes et Hut ont proposé en 1986 un algorithme dont la complexité est O(N.log N). Pour N=1′000′000, il n’y a environ que 20′000′000 de forces à évaluer, ce qui rend le calcul possible. L’algorithme consiste à diviser l’espace en une structure arborescente appelée octree et à y répartir les corps. On ne calcule les forces qu’entre les corps situé dans la même zone de l’octree, puis l’algorithme calcule les interactions entre les zones. Reste une difficulté : en se déplaçant, les corps changent de zone, et l’algorithme nécessite d’adapter l’octree de l’adapter à la distribution des corps.
interaction de 2 amas de 50 galaxies. N=160′000
Dès 1987, Leslie Greengard a développé un algorithme baptisé “Fast Multipole Method” (FMM), dont la complexité est O(N) seulement, et qui ne nécessite pas d’adaptation de la division de l’espace utilisée. Il est assez facile d’illustrer cette méthode en 2D, mais en 3D l’interaction entre zones est beaucoup plus complexe.
La FMM est considérée par certains comme l’un des algorithmes les plus importants du XXième siècle, car il peut être appliqué à des problèmes beaucoup plus généraux que les N corps, comme certains problèmes de mécanique des fluides ou de mécanque traités jusqu’ici par des méthodes de type “éléments finis” ou de simulation de molécules. Inutile de dire que je vais regarder ça de plus près …
Références:
- NEMO A Stellar Dynamics Toolbox, le logiciel développé par Barnes et Hut, site avec énormément de liens sur le domaine
- Dossier “le chaos dans le système solaire” sur AstroSurf
- Problème à N corps sur la Wikipedia
- N-body Methods à Berkeley
- The Art of Computational Science
- VPNBody : code VPython
- Fast Multipole Method sur Wikipedia
- Guy Blelloch and Girija Narlikar “A Practical Comparison of N-Body Algorithms” Parallel Algorithms. Series in Discrete Mathematics and Theoretical Computer Science, Volume 30, 1997.
- CUNBody, une librairie de simulation N corps parallélisée sur GPU (processeur graphique)
- Parallel N-Body Simulations : comparaisons et implémentation sur super ordinateurs
Logiciels N corps sur PC:
- Universe Sandbox : le plus beau et le plus fun
- Gravit : utilise l’alogrithme de Barnes Hut
- AstroGrav
- Gravity 6
- Gravity Simulator, un peu ancien