Application de MPFR et MPC à la mécanique célestezimmerma/cnc2_trip.pdf · Interface avec les bibliothèques dynamiques (DLL), telles que lapack, ... . Ecole d’été CNC’2,

Ecole d’été CNC’2, 2009 © M. Gastineau, Observatoire de Paris/IMCCE/CNRS

Application de MPFR et MPC à la mécanique céleste

M. Gastineau

IMCCE - Observatoire de Paris - CNRS UMR802877, avenue Denfert Rochereau

75014 PARISFRANCE

[email protected]

http://www.imcce.fr/Equipes/ASD/trip/trip.html

http://www.imcce.fr/Equipes/ASD/trip/trip.html


Plan

Preuve de stabilité linéaire du “Huit”

Intégration de MPC dans le système de calcul formel TRIP

Mouvement d’un satellite artificiel


Un petit bug...

compilateur intel fortran 10.1 64 bits

Opérateur ** retourne une valeur incorrecte en quadruple précision

Issue Q518258 ➡ corrigé seulement en version 11 !

Manque de tests des librairies constructeurs pour la quadruple

program monbug real(16) X, Y read(*,*) X,Y write(*,*) (X**Y) write(*,*) sqrt(X) stopend

X = 2 , Y = 0.51.41421356237309504876378807303183 1.41421356237309504880168872420970


Le problème des N corps

Déterminer les mouvements dans l’espace de N masses ponctuelles exerçant l’une sur l’autre une force attractive proportionnelle au produit de leurs deux masses et inversement proportionnelle au carré de leur distance.

Ici, masses égales unitaires

constante de gravitation G = 1

Equations du mouvement

q =N!

i !=j=1

(qj ! qi)||qi ! qj ||3

qi ! Rn


Premières solutions remarquables du problème des 3 corps

N = 3

Solutions explicites “à formes constantes”

• Euler (1765) et Lagrange (1772)


Le “Huit”

Chorégraphie avec N corps de période T = solution de l’équation où tous les corps se déplacent sur la même courbe avec un décalage constant de T/N.

Figure du “Huit” (Chenciner et Montgomery, 1999)


Le “Huit”

Chorégraphie avec N corps de période T = solution de l’équation où tous les corps se déplacent sur la même courbe avec un décalage constant de T/N.

Figure du “Huit” (Chenciner et Montgomery, 1999)



T. Kapela et C. Simo (2006)

Preuve assistée par ordinateur

Recherche de solutions telles que

au temps T/N

Recherche d’un point fixe x de la fonction

⇔ recherche d’un zéro de la fonction

x = (q1, q1, q2, q2, ..., qN , ˙qN )x = (qN , ˙qN , q1, q1, ..., qN!1, ˙qN!1)

G(x) = ! · "(x, T/N)

F (x) = G(x)! x = 0


Méthode de Krawczykopérateur de Krawczyk

avec

théorème

méthode itérative

K(x,X, F ) = x! CF (x) + (Id! C[DF (X)])(X ! x)

X ! Rn ensemble d’intervallex " XC " Rn isomorphisme lineaireF : Rn # Rn fonction C1

1. si x! ! X et F (x!) = 0, alors x! ! K(x,X, F )2. si K(x,X, F ) " int(X), alors il existe un unique x! ! X tel que F (x!) = 0

Xn+1 := K(x0, Xn, F ) avec X0 = x0 + [!1e! 12,+1e! 12]


Section de PoincaréCaractérisation de la stabilité des mouvements

φ(t,x*0) trajectoire de la solution x*(t) correspondant à la trajectoire correspondant à la condition initiale x*(0)= x*0.

Ecart entre les deux trajectoires à t = T est lié à l’écart à t=0

matrice 8x8 de monodromie du système différentiel : A

!"(T, x!0)!x0

=

!

""#

!"1

!x10

... !"1

!xn0

......

!"n

!x10

... !"n

!xn0

$

%%&


Stabilité linéaire du “Huit”

Valeurs propres déterminent la stabilité des orbites

4 valeurs propres ( ) égales à 1 : intégrales premières

polynôme caractéristique

avec

avec

T1 = !1 + !2, T2 = !3 + !4

!

! = trace(A)," =!

i!i<j!8

(aiiajj ! aijaji)

P = (!− 1)4(!− !1)(!− !2)(!− !3)(!− !4)P = !8 − (T1 + T2 + 4)!7 + (T1T2 + 4(T1 + T2) + 8)!6

det(A! !I) = !8 + "!7 + #!6 + ...

!1,!2,!3,!4 di!erentes, non reelles et !1 = !!12 = !2,!3 = !!1

4 = !4


Stabilité linéaire du “Huit”

T1 et T2 doivent être solution de

Il faut vérifier

T1 = !1 + !2, T2 = !3 + !4

! =( !! 4)2 ! 4(" ! 4! + 8) > 0, |T1| < 2, |T2| < 2

T 2 ! (!! 4)T ! 4(" ! 4! + 8) = 0


Arithmétiques d’intervalle

Représentation d’un nombre réel par un intervalle qui le contient

Définition d’un intervalle

Opération de base

! ! [3.1415, 3.1416]

[a, b] = {x|a ! x ! b}

x! y = {x! y|x " x, y " y}

! = {+,",#,÷}


Arithmétique d’intervalle : addition/soustractionAddition

Soustraction

z = x + y = [x + y, x + y]

typedef struct { mpfr_t left; mpfr_t right;} mpfrint_t;

mpfrint_t x, y, z;

mpfr_add(z.left, x.left, y.left, GMP_RNDD);mpfr_add(z.right, x.right, y.right, GMP_RNDU);

[0, 1]! [0, 1] = [!1, 1]

z = x! y = [x! y, x! y]


Résultats numériques

x0 + [!1e! 12,+1e! 12]

mantisse (bits) 53 60 65 70

! echec 7.0640916413346.376915708970 6.730985841465

10020195455 6.720873506910132528788

T1 de l’ 2.0303004115451.963251951280 1.998222059495

6177080558 1.997236101003163826379

T2 iteration !0.56124532213!0.62829378239 !0.594170451411

6215430349 !0.595157197233229471857

x0 = ( +1.0761437335109250,+0.4682662184090647,

−0.5380718667554619,−0.3437068277582447,

−1.0996037520751980,−0.2341331092045306)

!1,2 ! 0.99859998± 0.05289683i,!3,4 ! 0.29759667± 0.95469169i

Valeurs propres proches de 1


Plan


Intégration de MPFR/MPC dans le système de calcul formel TRIP



TRIPTRIP : système de calcul formel dédié à la Mécanique Céleste (J. Laskar, 1988-2009, M. Gastineau, 1998-2009)

Langage de programmation + interpréteurboucles, macros, conditions, ...

Séries formelles à plusieurs variables.utilisation de variables angulaires

Noyau parallelisé sur SMP.

Opérateur usuels (+,*, inversion), substitution, dérivation, intégration, évaluation, ...

Gestion automatique ou manuelle de l’ordre des variables.

Troncatures.

Fonctions dédié à la Mécanique Céleste: crochet de Poisson, r/a, cos E, ...

Interface avec les bibliothèques dynamiques (DLL), telles que lapack, ... .


Exemples de problèmes traitésDéveloppements en séries

• Etude de la stabilité du problème des 3 corps

• Etude de la dynamique du problème planétaire

Traitements numériques issus d’intégrations numériques des systèmes planétaires

• double-précision pas suffisante !


Architecture de TRIP

Representation of polynomial

Module numérique

(type Matlab)

Gnuplot

Module formel

Maple

Calcul

en

série creuse

Calcul

en

série pleine

Calcul

en

bloc homogène

Grace

Numerical kernel

(like matlab)

MathML

Symbolic kernel

Recursive

list

Recursive

vector

Homogeneous

blocks

D!Alembert

blocks

Fourier

blocks

Flat

vector

Objects

managerCelestial Mechanics

library

Memory

manager

Communication

manager

Fixed length

rational number

library

quadruple-precision

floating-point number

library

multiple-precision

floating-point number

library

MPFR, MPC

multiple-precision

rational number

library

GMP

Interval arithmetic

library

SCSCP C Library

Command interpreter (written in flex/bison)

Abstract syntax tree interpreter

User command parserMathML parser


Performances“Parallel Sparse Polynomial Multiplication Using Heaps” (ISSAC 2009)(Monagan, Pearce, 2009)

f = (1 + x + y + z + t)30h = f ! (f + 1)

Logiciel Temps (secondes)SDMP - 1 thread 71.59SDMP - 4 threads 11.48TRIP - 1 thread 92.39TRIP - 4 threads 23.76Magma 2.15-8 526.12Pari/GP 2.3.3 642.74Singular 3.1.0 744.00Maple 13 5849.48


Benchmarks

Type Size (bytes)double precision floating-point 13739456quadruple precision floating-point 19771328multiple precision floating-point (mpfr t) (significand = 53bits) 34851008multiple precision floating-point (mpfr t) (significand = 200bits) 58978496double precision floating-point interval 19771328quadruple precision floating-point interval 25803200multiple precision integer (mpz t) 22915568

P (x, y, z, t, u) = (1 + x + y + z + t + u)31

Type Execution time (s)double precision floating-point 4quadruple precision floating-point 20multiple precision floating-point (mpfr t) (significand = 53bits) 96multiple precision floating-point (mpfr t) (significand = 200bits) 110double precision floating-point interval 83quadruple precision floating-point interval 108multiple precision integer (mpz t) 15


Benckmarks

P (x, y, z, t, u) = (1/2ı+3/5x+ y +(1+7/11ı)z +13/17t+(31+21/29ı)u)31

Type Size (bytes)double precision floating-point 13739456quadruple precision floating-point 25753152multiple precision floating-point (mpc t) (significand = 53bits) 55787392multiple precision floating-point (mpc t) (significand = 200bits) 103842176double precision floating-point interval 25753152quadruple precision floating-point interval 37766848multiple precision integer (mpq t) 61389176

Type Execution time (s)double precision floating-point 8quadruple precision floating-point 97multiple precision floating-point (mpc t) (significand = 53bits) 363multiple precision floating-point (mpc t) (significand = 200bits) 1964double precision floating-point interval 235quadruple precision floating-point interval 431multiple precision rational (mpq t) 2056


Implémentation du multi-threading dans TRIP

Chaque thread gère une queue de travail

modèle : Work stealing

Processor 0 Processor 1 Processor 2 Processor 3

Process TRIP

memory

Threadworker 0

Threadworker 1

Threadworker 3

Threadworker 2

Main Thread

Thread 0idle

Thread 1idle

Thread 3working

Thread 2idle

WORK shareable work

WORK shareable work


MPFR/MPC et multi-threadingAppel des routines de MPFR et MPC par plusieurs threads

MPFR installé avec le système linux

0

0,25

0,50

0,75

1,00

1 2 3 4

double

nombre de threads

temps cputemps horloge

0

2,5

5,0

7,5

10,0

1 2 3 4

mpfr_t

nombre de threads

(1 + x + y + z + t)22 ! ((1 + x + y + z + t)22 + 1)


MPFR/MPC et multi-threading

Variables globales

Recompilation de MPFR : ./configure --enable-thread-safe

0

0,25

0,50

0,75

1,00

1 2 3 4

double

nombre de threadstemps cputemps horloge

0

0,25

0,50

0,75

1,00

1 2 3 4

mpfr_t

nombre de threads


MPFR/MPC et la mémoire

Réels alloués par les routines de GMPpar défaut : malloc/free

Si précision identique ➡ allocation d’objets de même taille

utilisation de routines optimisées

produit de 2 polynômes : 200000 réels alloués

/*! fonction "malloc" utilise par gmp. cf.trp_gmp_setmemfunctions */

void * trp_gmp_alloc (size_t alloc_size)

{ ... }

/*! fonction "free" utilise par gmp. cf.trp_gmp_setmemfunctions */

void trp_gmp_free (void *ptr, size_t size)

{ .... }

/*! fonction "realloc" utilise par gmp. cf.trp_gmp_setmemfunctions */

void* trp_gmp_realloc (void *ptr, size_t old_size, size_t new_size)

{ ... }

/*! enregistre les fonctions personnalises d'allocation pour gmp */

void trp_gmp_setmemfunctions(void)

{

mp_set_memory_functions(trp_gmp_alloc,trp_gmp_realloc,trp_gmp_free);

}

OS temps (secondes) temps (secondes)malloc/free allocation specialisee

Linux 88 72Mac OS X 58 50


Intégration de MPFR/MPC dans TRIP

Utilisation des types mpfr_t et mpc_t similaires aux types scalaires

C++ large utilisation des template et de la spécialisation

• Généricité des fonctions : opérations, alogrithmes, ...

• Généricité des classes : vecteurs numériques

6000 lignes spécifiques à MPFR/MPC

Allocation optimisée pour les réels ayant une petite taille < 32 octets


Problème des 3 corps restreint


Problème des 3 corps restreint


Problème des 3 corps restreint - calcul de forme normale

H(px, py, pz, x, y, z) =12(p2

x + p2y + p2

z) + ypx ! xpy +!

12! µ

"x!

"3

2y ! 1! µ

rPS! µ

rPE

r2PS = (x! xS)2 + (y ! yS)2 + Z2

coordonnées

Hamiltonien au point L5

Développement de 1/rPS et 1/rPE en polynôme de Legendre

An+1 =2n + 1n + 1

(xxS + yyS)An !n

n + 1(x2 + y2 + z2)An!1

A0 = 1 et A1 = xxS + yyS

x, y, z : position de la particule

xS , yS , 0 : position du soleil

xE , yE , 0 : position de la Terre

µ : rapport des masses


Problème des 3 corps restreint - calcul de forme normaleAprès développement

Changement de variables

Nouvel hamiltionien

H(px, py, pz, x, y, z) = !1 +12(p2

x + p2y + p2

z) + ypx ! xpy

+18x2 ! 5

8y2 ! 3

"3

4(1! 2µ)xy +

12z2 + ...

!

""""""#

xpx

ypy

zpz

$

%%%%%%&= M

!

""""""#

q1

p1

q2

p2

q3

p3

$

%%%%%%&

M matrice 6x6 a coe!cients complexes

H =!"1w1q1p1 +

!"1q2p2 +

!"1q3p3 + ...


Exemple de traitement numérique 1/2

Ephémérides INPOP intégrées en précision étendue (64 bits)

Distribution des éphémérides sous la forme de polynômes de Tchebychev

Manipulation du temps en jours julien

• 26/06/2009 9h00m00s ⇔ jour julien 2455008.875

• 26/06/2009 9h00m01s ⇔ jour julien 2455008.875011574

• Erreur de -5.4240226745605469e-6 secondes ➡ erreur en position de 16 cm sur la lune

• Précision supérieure nécessaire !


Plan


Intégration de MPC dans le système de calcul formel TRIP




satellite artificiel autour de la Terre (San Miguel, 2006)

• prise en compte de

- effets gravitationnels de la Terre et du Soleil

- effets relativistes : aplatissement de la Terre


Equations du mouvement

V : potentiel gravitationnel

f : forces relativistes agissant sur le satellite

d2qdt2

= !V + f

f =6!

i=1

fi


Librairie MPFRCPPinterface C++ pour MPFR

mpfr_t ➔ Real

Définition d’un mode d’arrondi par défautOpérateur *,+,-,/ disponible

Appel de mpfr_init2 dans le constructeur

Library.setPrecision( Precision( 200 ) );

Real s ( 1 ), t ( 1 ), u; for ( unsigned int i = 1; i <= 100; i++ ) { t = Mul( t, i, roundTowardInfinity ); u = 1; u = Div( u, t, roundTowardNegInfinity ); s = Add( s, u, roundTowardNegInfinity ); }


Effet du pas d’intégration et de la précisionEnergie = constante : intégrale première du système

Intégration numérique (Runge-Kutta)utilisation de MPFR + MPFRCPP - précision : 36 chiffres

précision = 24 chiffres ➡∆E = 1.4E-17

précision = 15 chiffres ➡∆E = 2.2E-12


ConclusionEssayez TRIP...

http://www.imcce.fr/Equipes/ASD/trip/



Documents

Application de MPFR et MPC à la mécanique célestezimmerma/cnc2_trip.pdf · Interface avec les bibliothèques dynamiques (DLL), telles que lapack, ... . Ecole d’été CNC’2,