1.1.1: rur pour les systemes polynomiaux

Librairie C++ de calcul formel/ C++ symbolic computation library

Modérateur : xcasadmin

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

1.1.1: rur pour les systemes polynomiaux

Message par parisse » mer. avr. 16, 2014 1:25 pm

Je viens de finir le 1er jet d'une implementation de la representation univariee rationnelle pour les systemes polynomiaux ayant un nombre fini de solutions. Ca ne marche que si l'ideal est radical, et si le systeme est capable de trouver une forme lineaire en les variables permettant de separer toutes les solutions -> dans la grande majorite des cas, ca devrait notablement ameliorer la robustesse de solve/fsolve.
solve() utilise cette methode par defaut dans la 1.1.1, fsolve() appelle solve si le systeme est polynomial et si on n'a mis que 2 arguments.
On peut aussi appeler gbasis avec comme ordre rur (au lieu de revlex ou plex) pour obtenir en reponse une liste commencant par -4 puis la forme lineaire separante, puis le polynome minimal, puis sa derivee puis les variables en fonction de la variable separante.
Pour l'instant il faut compiler pour tester, mais je vais bientot faire les premiers binaires 1.1.1 (en testing).
Si vous avez des systemes a resoudre, ca pourrait etre bien de les tester avec le nouveau code...

frederic han
Messages : 1137
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: 1.1.1: rur pour les systemes polynomiaux

Message par frederic han » jeu. avr. 17, 2014 7:38 am

voici un petit exemple. normalement c'est 3 points pour I1 c'est probablement une extension de degre 3 et I2 de degre 2.

Code : Tout sélectionner

A:=[[x,y,z],[y,z,t]];
I1:=[seq(det(delcols(A,j)),j=0..2),x+2*y-3*z+4*t,t-1];
I2:=[seq(det(delcols(A,j)),j=0..2),x+y+z-3*t,t-1];
solve(I1,[x,y,z,t]);
solve(I2,[x,y,z,t]);
Macaulay2 donne:

Code : Tout sélectionner

i1 : A=QQ[x,y,z,t]

o1 = A

o1 : PolynomialRing

i2 : I2=ideal(y*t-z^2,x*t-z*y,x*z-y^2,x+y+z-3*t,t-1)

               2                        2
o2 = ideal (- z  + y*t, - y*z + x*t, - y  + x*z, x + y + z - 3t, t - 1)

o2 : Ideal of A

i3 : radical(I2)

                                                               2               
o3 = ideal (- t + 1, - y*t - 2z*t + y + 2z + 3t - 3, - y*z - 2z  + y - z + 3, -
     --------------------------------------------------------------------------
      2                                                                       
     y  - 2y*z - 2y + 2z + 3, - x*y - 2x*z - 3x + y + 2z + 3, x*y + 2x*z - y*z
     --------------------------------------------------------------------------
         2                         2     3           2
     - 2z  - 3x - 6y - 9z + 18, y*z  + 2z  + 2y*z + z  + 3y - 9)

o3 : Ideal of A

i4 : radical(I2)==I2

o4 = true

i5 : decompose(I2)

                                            2
o5 = {ideal (y + 2z + 3, t - 1, x - z - 6, z  + 2z + 3), ideal (z - 1, y - 1, t
     --------------------------------------------------------------------------
     - 1, x - 1)}


parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 1.1.1: rur pour les systemes polynomiaux

Message par parisse » jeu. avr. 17, 2014 9:05 am

J'ai bien 3 points, complexes pour I1, 2 complexes et 1 reel pour I2, pour i1 ca donne des rootof, pour i2 le resultat est comprehensible par tout le monde.
Je suis en train de compiler des binaires...

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 1.1.1: rur pour les systemes polynomiaux

Message par parisse » jeu. avr. 17, 2014 9:15 am

P.S.: je me documente sur tout ca, du coup j'ai une question: si l'ideal n'est pas radical, on peut le detecter par le fait que le polynome minimal de chacune des variables n'est pas sqrfree, dans ce cas si j'ai bien compris en ajoutant la partie sqrfree de chaque polynome minimal a l'ideal on obtient un ideal radical, du coup j'ai un test de radicalite (puisque je teste toutes les variables comme forme lineaire separante donc je calcule deja tous les polynomes minimaux), mais je peux aussi facilement modifier la base de Groebner en y ajoutant les parties squarefree des polynomes minimaux des variables et donc me ramener a un ideal radical pour chaque nombre premier choisi (lorsque la dimension du quotient par l'ideal diminue). La question c'est quel est le risque de mauvais nombre premier (i.e. I est radical sur Q mais pas modulo p)?

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 1.1.1: rur pour les systemes polynomiaux

Message par parisse » jeu. avr. 17, 2014 12:11 pm

J'ai trouve une base de donnees de systemes polynomiaux sur le site de Jan Verschelde:
http://www.math.uic.edu/%7Ejan/Demo.tar.gz
il y a de quoi s'occuper...

frederic han
Messages : 1137
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: 1.1.1: rur pour les systemes polynomiaux

Message par frederic han » ven. avr. 18, 2014 7:22 am

Salut,
si j'ai bien compris ce que tu fais, tu as un I ideal sur Q et tu choisis un nombre premier p puis tu trouves un generateur g_(i,p) de I mod p inter Fp[x_i] pour chaque variable x_i. Le but etant de remonter g_(i,p) vers g_i generateur de I inter Q[x_i], mais le calcul du radical de I mod p ne t'interesse pas vraiment (car il peut etre un peu plus gros que de juste rajouter ces pol min), c'est celui de I que tu veux.

Dans le cas ou g_(i,p) n'est pas reduit n'as tu pas plus vite fait de le remonter tout de meme dans Q puis de prendre son radical en caracteristique 0?

En effet, si tu prends le radical de g_(i,p) alors que g_i etait en fait reduit (ie mauvais p) tu n'arriveras pas a le remonter ds Q, donc j'ai plutot l'impression que la probabilite qui te genes est celle ci:
il existe i tq le pol min de x_i ds Fp[x....]/(I mod p) n'est pas reduit.

Fred

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 1.1.1: rur pour les systemes polynomiaux

Message par parisse » ven. avr. 18, 2014 9:22 am

je ne calcule pas la base de Groebner sur Q, et je ne calcule les polynomes minimaux pour toutes les variables que si je n'en trouve pas qui me donne un degre egal au degre du quotient. Dans ce cas je calcule la partie sqrfree de chaque polynome minimal, et je recalcule la base de l'ideal engendre, ca ne doit pas couter trop cher je pense, puisqu'on a presque une base de Groebner du radical...
bon, en fait il me semble que le probleme des mauvais premiers doit se resoudre en comparant la liste des monomes dominant de l'ideal radical, si pour des premiers differents l'une des listes contient l'autre, alors il faut jeter le premier qui a la liste incluse, et garder l'autre premier.

Répondre