Page 1 sur 2
1.2.2 eliminate
Publié : mer. févr. 03, 2016 7:22 pm
par frederic han
Je ne sais pas si c'est un bug ou si c'est voulu, mais elimate me semble bien plus lent avec giac 1.2.2-27 qu'avec 1.2.1
Ex:
Code : Tout sélectionner
L:=[-2*x0^3 - 21*x0*x1^2 + 5*x1^3 + 31*x0^2*x2 + 26*x0*x1*x2 + 9*x1^2*x2 + 21*x0*x2^2 + 15*x2^3 + 8*x0*x1 - 27*x1*x2, 33*x0^3 + 10*x0^2*x1 + 7*x0*x1^2 + 41*x0^2*x2 + 46*x0*x2^2 - 36*x1*x2^2 + 24*x2^3 + 3*x0^2 + 32*x1^2 + 40, 44*x0*x1^2 + 46*x1^3 - 37*x0*x1*x2 + 13*x1^2*x2 - 24*x0*x2^2 + 44*x1*x2^2 - 35*x2^3 + 14*x0^2 + 2*x0 - 15*x2];
B:=eliminate(L,[x1,x2]);
Comme si giac 1.2.2 n'utilisait pas les ameliorations de giac 1.2.1
Fred
Re: 1.2.2 eliminate
Publié : jeu. févr. 04, 2016 7:14 am
par parisse
Je pense plutot que c'est un cas ou l'algorithme f4 n'est pas adapte, et en plus il y a peut-etre un overflow dans un exposant intermediaire. En tout cas je vais rajouter une option resultant a eliminate qui permettra de forcer l'utilisation du resultant.
Re: 1.2.2 eliminate
Publié : jeu. févr. 04, 2016 8:23 am
par frederic han
OK,
NB: avec 1.2.1 c'est immediat. Tu veux dire que 1.2.1 utilisait le resultant?
Re: 1.2.2 eliminate
Publié : jeu. févr. 04, 2016 10:04 am
par parisse
non, je pense qu'il y a un bug dans les optimisations que j'ai ajoutees pour l'ordre.
Re: 1.2.2 eliminate
Publié : jeu. févr. 04, 2016 5:08 pm
par parisse
Bon, il y avait bien un bug dans l'ordre, mais le probleme est ailleurs. C'est la strategie de selection des paires qu'il faut que je reprenne lorsqu'il y a elimination, car le degre total d'un polynome n'est plus le degre total de son coefficient dominant pour l'ordre double revlex. Du coup c'est peut-etre un bug qui va permettre de faire avancer le schmillblick.
Re: 1.2.2 eliminate
Publié : mer. févr. 10, 2016 2:18 pm
par frederic han
Est ce que la situation a evoluee dans la version instable?
J'ai teste giac 1.2.2-29 et cette fois j'arrive a faire en 11s l'elimination mais avec giac 1.2.1 c'etait 0.05s. (avec une difference c'est que giac 1.2.1 m'affiche un warning de reconstruction probabiliste et pas 1.2.2)
Re: 1.2.2 eliminate
Publié : mer. févr. 10, 2016 4:20 pm
par parisse
Je ne pense pas qu'on pourra retrouver le temps observe pour la 1.2.1, parce que la strategie de selection des paires utilisait le degre partiel par rapport aux variables a eliminer. C'est plus rapide dans ce cas-la, mais pas du tout sur beaucoup d'autres exemples. Pour le moment, j'utilise le degre total par rapport a toutes les variables, et le nombre d'iterations de f4 a effectuer depasse la limite (maintenant fixee a 512), donc l'algorithme modulaire echoue et repasse la main a Buchberger classique sur Q (qui utilise des structures de donnees pas optimisees). J'ai essaye une strategie de selection de degre mixte, mais ca ne marche pas vraiment mieux.
Je pourrais bien sur reduire le temps en diminuant le nombre d'iterations autorisees pour f4 pour avoir un echec plus rapidement et donner la main a Buchberger classique, mais certains autres calculs risquent alors de ne plus passer. Au final, il faudrait sans doute pouvoir donner un peu de choix a l'utilisateur pour la strategie de selection des paires, mais ce n'est pas evident a implementer.
Re: 1.2.2 eliminate
Publié : mer. févr. 10, 2016 7:15 pm
par parisse
J'oubliais: tu peux aussi appeler eliminate(..., resultant) qui dans ce cas va plus vite, mais il sort un facteur en trop.
Re: 1.2.2 eliminate
Publié : ven. févr. 12, 2016 1:08 pm
par frederic han
parisse a écrit :Je ne pense pas qu'on pourra retrouver le temps observe pour la 1.2.1, parce que la strategie de selection des paires utilisait le degre partiel par rapport aux variables a eliminer. C'est plus rapide dans ce cas-la, mais pas du tout sur beaucoup d'autres exemples.
Comment sont les exemples ou giac 1.2.2 est meilleur que giac 1.2.1 pour eliminate? Pour l'instant je n'ai rien de clairement favorable a 1.2.2.
Fred
Re: 1.2.2 eliminate
Publié : ven. févr. 12, 2016 2:47 pm
par parisse
Il s'agit des exemples de la base de tests de geogebra
https://dev.geogebra.org/trac/browser/t ... c/src/test
Avec plus de variables a eliminer.
Maintenant s'il y a une raison qui permette de dire que la strategie degre partiel est meilleure en fonction de l'input (par exemple nombre de variables), on peut la changer dans ce cas.
Re: 1.2.2 eliminate
Publié : lun. févr. 15, 2016 10:28 am
par frederic han
Les equations de geogebra sont particulierement simples par rapport au grand nombre de variables (souvent plus de 15 et tres majoritairement des quadriques avec tres peu de termes) J'obtiens effectivement sur les exemples de heavy.txt que giac 1.2.2 est plus rapide que giac 1.2.1 (20%?)
mais il reste un probleme je pense qu'une bete intersection complete comme celle ci devrait passer:
Code : Tout sélectionner
eliminate([(-34*x0^3+21*x0^2*x2+13*x1^2*x2+20*x1*x2^2-30*x2^3-31*x0^2-34*x1^2+5*x0*x2-32*x0+33)*(1 % 101),(2*x1^3-29*x0^2*x2-3*x1^2*x2-48*x1*x2^2-14*x2^3-33*x0*x1+7*x1^2+21*x1*x2-10*x0+39*x2)*(1 % 101),(32*x0^3+38*x1^2*x2-34*x0*x2^2-35*x2^3+14*x0*x1-6*x1^2-43*x2^2-20*x0+42*x1-17)*(1 % 101)],[x1,x2])
ca met 0.03s avec giac 1.2.1 et
avec giac 1.2.2-29 j'ai un
Code : Tout sélectionner
// Groebner basis computation time 0.356268 Memory 0.023244M
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Re: 1.2.2 eliminate
Publié : lun. févr. 15, 2016 12:32 pm
par parisse
Je crois que j'ai une solution qui menage la chevre et le chou. J'utilise le degre total par defaut, mais si ca ne selectionne qu'une seule paire, j'incremente un compteur, si ce compteur atteint 5, alors je change de strategie en passant au degre des variables d'elimination seules. Sur tes exemples, ca passe a nouveau rapidement et ca n'a pas l'air d'affecter trop les tests de geogebra.
Les tests de geogebra sont des tests du systeme de preuve automatique de theoremes de geometrie euclidienne, c'est pour ca que les equations sont simples et les variables nombreuses.
Re: 1.2.2 eliminate
Publié : mar. févr. 16, 2016 10:36 am
par frederic han
avec la version instable du 15/2,
C'est mieux mais j'ai des messages bizarre en augmentant la difficulte:
Code : Tout sélectionner
L:=[-7*x0^2*x2 + 36*x0*x2*x3 + 44*x0*x3^2 + 36*x3^3 - 11*x0*x1 + 5*x1*x2 - 2*x0*x3 + 18*x2*x3 + 11*x1 - 33*x3, 16*x0*x1^2 - 39*x0*x2^2 - 20*x0^2*x3 + 50*x0*x2*x3 + 25*x2^2*x3 + 21*x0*x3^2 - 41*x0^2 + 33*x0*x1 - 21*x1*x3 + x3^2, 40*x0^2*x2 + 41*x0*x1*x2 - 14*x2^3 + 46*x1*x2*x3 + 22*x0*x3^2 + 16*x1*x3^2 + 36*x0*x1 - 22*x1*x3 + 38*x2*x3 + 47*x1, 5*x0*x1^2 + 26*x0*x1*x2 - 32*x1*x3^2 + 12*x3^3 + 28*x1^2 + 33*x1*x2 - 19*x1*x3 + 15*x3^2 - 33*x1 + 37*x3] % 101;
eliminate(L,[x1,x2,x3]);
donne
Code : Tout sélectionner
"Unable to compute gbasis with giac, perhaps dimension is too large Error: Bad Argument Value"
c'est voulu?
Re: 1.2.2 eliminate
Publié : mar. févr. 16, 2016 11:58 am
par parisse
En autorisant 512 iterations (apres modif de cocoa.cc), il apparait a la 348eme iteration des degres intermediaires tres grands, par exemple x0^8122, du coup c'est tres lent. En changeant de strategie pour la selection de paires, ca devient tres lent au bout d'un nombre d'iterations plus faible (172) mais ca n'aboutit pas a l'iteration 182 pour cause de depassement de degre.
Ca vient d'ou et c'est cense donne quoi?
Re: 1.2.2 eliminate
Publié : mar. févr. 16, 2016 12:58 pm
par frederic han
Pour faire quelques test,
j'ai pris n equations de degre 3 en n variables au hasard et j'en elimine n-1 donc ca devrait donner un polynome de degre 3^n si le hasard etait assez general. Comme maintenant ca marchait bien avec n=3 (rapide et meme reponse que singular) j'ai essaye n=4...
l'exemple que je t'ai donne ne semble pas assez generique. singular donne comme reponse:
Code : Tout sélectionner
Ideal (x0^66 - 16*x0^65 + 37*x0^64 + 31*x0^63 + 2*x0^62 - 47*x0^61 + 10*x0^60 + 3*x0^59 + 4*x0^58 - 25*x0^57 - 17*x0^56 - 3*x0^55 - 10*x0^54 - 4*x0^53 + 31*x0^52 - 46*x0^51 + 22*x0^50 - 3*x0^49 + 36*x0^48 + 27*x0^47 + 35*x0^46 + x0^45 - 28*x0^44 + 48*x0^43 - 45*x0^42 - 50*x0^41 + 8*x0^40 + 6*x0^39 - 7*x0^38 - 26*x0^37 + 47*x0^36 - 37*x0^35 - 39*x0^34 + 9*x0^33 + 31*x0^32 - 50*x0^31 + 28*x0^30 - 15*x0^29 - 33*x0^28 + 19*x0^27 + 45*x0^26 - 16*x0^25 - 18*x0^24 + 3*x0^23 + 31*x0^22 - 43*x0^21 - 35*x0^20 + 37*x0^19 + 11*x0^18 + 49*x0^17 + 23*x0^16 - 14*x0^15 + x0^14 - 4*x0^13 + x0^12 - 7*x0^11 + 37*x0^10 - 37*x0^9 - 39*x0^8 + 44*x0^7 - 11*x0^6 + 9*x0^5 + 10*x0^4 + 7*x0^3)
mais avec d'autres exemples, singular donne bien un poly de degre 81 et giac l'erreur de depassement.