Séminaire des équipes de recherche

Algorithmique de l'algèbre de décomposition universelle

  • Date : 11/06/2012
  • Lieu : Inria-Rocquencourt, salle de conférence du bâtiment 9
  • Intervenants : Romain Lebreton, LIX, École polytechnique.
  • Organisateurs : Equipe-projet Algorithms

Fixons un corps effectif k et un polynôme f dans k[T] de degré n. Nous appellerons relations symétriques les polynômes symétriques à coefficients dans k qui s'annulent sur les racines de f dans une extension appropriée. Ces relations forment un idéal I. L'algèbre de décomposition universelle est l'algèbre quotient A := k[X1 , …, Xn ] / I. Cette algèbre est liée au corps de décomposition L de f. Par exemple, pour des coefficients de f génériques, L s'identifie à A. Dans cet exposé, nous montrons comment obtenir une algorithmique efficace dans A. Pour cela, on utilise une représentation à une variable de A, c'est-à-dire un isomorphisme explicite de la forme A ~ k[T] / Q(T). Dans cette représentation, les opérations arithmétiques de A ont naturellement une complexité quasi-optimale. Nous détaillerons deux algorithmes intrinsèquement liés explicitant d'une part l'isomorphisme et d'autre part calculant le polynôme caractéristique d'un élément P de A. Puis nous parlerons des généralisations possibles de cette méthode. Travail en collaboration avec Éric Schost.

Mots-clés : ALGORITHMS Séminaire

Haut de page

Siège et centres de recherche Inria

Accès direct

Social