Séminaire LJK-Modèles et Algorithmes Déterministes: CASYS

 

Le Jeudi 31 Janvier 2002 à 9h45 en Salle 1 - Tour IRMA

 

Séminaire de Nicolas THIERY (Lyon 1)

 

Calculs d'invariants de groupes de permutations, via les bases SAGBI-Gröbner

 

Résumé:

 

La théorie des bases de Gröbner, qui permet de calculer avec des idéaux d'algèbres de polynômes, a été étendue dans la dernière décennie aux sous-algèbres d'algèbre de polynômes (bases SAGBI), et à leurs idéaux (bases SAGBI-Gröbner). Elle permet en particulier de faire certains calculs sur des polynômes en respectant les symétries. Lorsque ces symétries proviennent d'un groupe de permutations, nous avons remarqué que cette théorie prenait un aspect particulièrement effectif; elle permet en effet de clairement dissocier la partie purement combinatoire, qui contient les symétries du problème, de l'algèbre linéaire, qui est similaire à celle utilisée par exemple dans le logiciel de calcul de bases de Gröbner Fgb. Dans ce cadre, nous présentons un nouvel algorithme permettant de calculer un système générateur minimal de l'algèbre des invariants d'un groupe de permutations. Implanté dans la bibliothèque PerMuVAR du système de calcul formel MuPAD, il s'avère, en pratique et dans de nombreux cas, bien plus efficace que les algorithmes classiques de théorie des invariants. L'utilisation de bibliothèques d'algèbre linéaire creuse comme linbox (développé entre autres par Jean-Guillaume Dumas) promet de substanciels progrès supplémentaires.