Devoir Maison 2013 – FGLM

Un algorithme de changement d’ordre prend en entrée une base de Gröbner pour un ordre $<_1$ et un autre ordre $<_2$, et donne en sortie une base de Gröbner pour $<_2$. Ces algorithmes ont une importance toute particulière pour le calcul de bases de Gröbner pour l’ordre lex, en effet il arrive souvent qu’en pratique il soit moins coûteux de calculer une base pour l’ordre degrevlex, et ensuite de convertir celle-ci en une base pour lex, que de calculer directement cette dernière.

L’algorithme FGLM (d’après les noms de ses auteurs : Faugère, Gianni, Lazard, Mora), est le premier de ces algorithmes à avoir été proposé. Il permet d’effectuer des changements d’ordre quelconques pour les idéaux zéro-dimensionnels en temps cubique en le degré de l’idéal. Le but de ce DM est d’implanter une version simplifiée de cet algorithme.

Références

On utilisera comme références la description de l’algorithme qui est faite à la section 2.3 du livre Using Algebraic Geometry de Cox, Little et O’Shea. On pourra aussi regarder ces transparents de J.-C. Faugère, qui décrivent l’algorithme simplifié aux pages 25 et 26. Encore une référence utile est le Chapitre 6 du livre Mathématiques appliquées, par J.-C. Faugère et M. Safey el Din, que les auteurs mettent librement à disposition (l’algorithme simplifié y est décrit à la page 38). Enfin les plus curieux pourront regarder le papier original, plus dur à lire.

Consignes

Implantez en Sage la version simplifiée de l’algorithme FGLM, telle que décrite dans l’une des références ci-dessus, en vous conformant aux points suivants.

• Fournissez une fonction fglm(GB, order) qui prend en entrée :

  • Une base de Gröbner GB (une liste de polynomes, telle que renvoyée par la méthode .groebner_basis() utilisée en TD ; l’ordre monomial est donné implicitement par le parent commun des polynômes) ;

  • Un ordre monomial order. Ceci peut-être, au choix, un objet de la classe TermOrder, ou bien une fonction qui prend en entrée deux monômes et qui renvoye le résultat de la comparaison ;

  et qui donne en sortie une base de Gröbner pour l’ordre order.

• Fournissez des exemples de bases de Gröbner pour plusieurs ordres différents, et comparez la sortie de votre algorithme avec le résultats calculés par la méthode .groebner_basis(). À cet effet, vous pourrez vous servir de la méthode .change_ring() pour changer l’ordre par défaut d’un anneau de polynômes. Elle s’utilise comme ceci :

  sage: R.<x,y> = PolynomialRing(QQ, order='lex')
  sage: S = R.change_ring(order='degrevlex')         # S est une copie de R
                                                     # avec un ordre différent
  sage: I = R.ideal(x^2 - y, y^3 + x*y)              # un idéal de R
  sage: J = I.change_ring(S)                         # le même idéal pour un
                                                     # ordre différent
  sage: I == J
  True
  sage: I.groebner_basis() == J.groebner_basis()
  False
  

• Votre devoir doit être rendu dans l’une des formes suivantes :
  • fichier .sage contenant les fonctions et les tests,
  • feuille de calcul Sage, exportée au format .sws,
  • lien vers une feuille de calcul sur http://sage.math.uvsq.fr/.
• Mettez des commentaires dans votre code : cela m’aide dans la correction.

Conseils

Il peut être commode d’écrire une fonction auxiliaire qui prend en entrée une liste de polynômes $g_1,\ldots,g_i$ et un polynôme $f$ et qui renvoie, s’ils existent, les coefficients $\lambda_i$ d’une combinaison linéaire

$$\lambda_1 g_1 + \cdots + \lambda_i g_i = f.$$

Servez-vous le plus possible des fonctions déjà disponibles dans Python et dans Sage. Les sections suivantes du manuel vous seront particulièrement utiles :

• Structures de données en Python,
• Anneaux multivariés,
• Matrices.

Vous êtes jugés sur la qualité de votre code. Préférez un code compact, lisible, et pythonique (tapez import this dans Sage). Pour comparaison, mon implantation de l’algorithme simplifié tient en 28 lignes (de moins de 80 caractères), commentaires exclus.

Question bonus

Implantez la version matricielle de FGLM. Cette version est décrite dans les transparents de Faugère et dans le livre de Faugère et Safey el Din. Sa caractéristique principale est le remplacement de toutes les divisions de polynômes par des produits matrice-vecteur, ce qui permet d’atteindre la complexité cubique annoncée au début.