bases de groebner

Nouveautes concernant Xcas.
News about Xcas

Modérateur : xcasadmin

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

bases de groebner

Message par parisse » ven. oct. 30, 2015 6:06 pm

J'ai mis en ligne une version 1.2.2 du source http://www-fourier.ujf-grenoble.fr/~par ... .2.tar.bz2, qui permet sur mon mac
- de resoudre cyclic9 sur Q en 10h de temps CPU, 5h de temps reel avec 2 coeurs.
- de resoudre cyclic10 modulo un premier de 24 bits en 63000s (14G de memoire necessaires)
Je ferai sans doute en debut de semaine prochaine des binaires instables.

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

Re: bases de groebner

Message par frederic han » lun. nov. 02, 2015 3:06 pm

Superbe!
J'ai commence quelques essais, je remarque que maintenant il y a aussi de la parallelisation dans un corps fini.
Pour cyclic9 dans GF(101) sous sage avec 8threads je passe (entre giac 1.2.0 et 1.2.2)
de

Code : Tout sélectionner

Time: CPU 1328.82 s, Wall: 1328.61 s
Polynomial Sequence with 1344 Polynomials in 9 Variables
a

Code : Tout sélectionner

Time: CPU 824.29 s, Wall: 326.89 s
Polynomial Sequence with 1344 Polynomials in 9 Variables

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

Re: bases de groebner

Message par parisse » lun. nov. 02, 2015 4:12 pm

Ca parait gros, peut-etre a cause de la conversion vers sage? Sur un quad-core i5, j'ai CPU 382, real 272 avec 2 threads, et pas tellement mieux avec 4 threads: CPU 571, real 262. Je suis en train d'essayer cyclic10 modulaire avec 2 threads, mais pas sur que ca passe sur ce PC qui n'a que 8Go de ram et 8 Go de swap.
Je me suis apercu que j'avais un assez bon gain de temps en modulaire pour les cycliques en renvoyant a la fin la reduction de certaines paires qui ont le meme LCM et l'element d'indice le plus faible en commun (i.e. des paires i<j et i<k avec lcm(i,j)==lcm(i,k)). Elles ne verifient pas les criteres de Gebauer-Moller, et pourtant elles semblent se reduire a 0 quand meme a la fin (ce serait bien de savoir prouver qu'elles se reduisent a 0 ca permettrait de gagner du temps a la fin!). Cette optimisation n'est par contre pas interessante pour katsura, et curieusement pas non plus pour cyclic rationnel.

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

Re: bases de groebner

Message par frederic han » mar. nov. 03, 2015 10:43 am

Non c'est le serveur qui est ancien Xeon E5520@2.27Ghz (2 cpu physiques de 4 cores). Pour un calcul sans memoire ni disque mon portable agé de 2ans est plus rapide, la conversion sur ces temps me semble inférieure a 30s. Mais sur cette machine avec ou sans conversion j'ai des temps totaux similaires entre giac 1.2.2 et magma 2.20-10 sur cyclic9 mod 101 (cette version de magma ne parallelise pas)

J'ai eu avec giac1.2.2 cyclic10 modulo prevprime(2^24) (avec conversion vers sage) en 10h de temps total /46.5htemps cpu alors qu'avant avec giac 1.2.0, sans conversion vers sage il avait fallut 52h.

Je n'ai pas encore teste des exemples moins types. Il y a t'il un impact sur l'elimination?

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

Re: bases de groebner

Message par parisse » mar. nov. 03, 2015 11:28 am

Ca devrait au moins en partie, la parallelisation concerne l'algebre lineaire de F4. Mais certaines optimisations ne sont pas parallelisees et le stockage des monomes est plus optimise pour revlex que pour des ordres d'elimination.

Répondre