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.

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 :

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.

Fork me on GitHub