1.2.2 eliminate

[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

[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.

[frederic han]

OK,
NB: avec 1.2.1 c'est immediat. Tu veux dire que 1.2.1 utilisait le resultant?

[parisse]

non, je pense qu'il y a un bug dans les optimisations que j'ai ajoutees pour l'ordre.

[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.

[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)

[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.

[parisse]

J'oubliais: tu peux aussi appeler eliminate(..., resultant) qui dans ce cas va plus vite, mais il sort un facteur en trop.

[frederic han]

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

[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.

[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

[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.

[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?

[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?

[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.