Séminaire Maths-InfoRSS

Résolution des Systèmes Polynomiaux par les bases de Gröbner


25/03/2013
Intervenant(s) : Jean-Charles FAUGÈRE (INRIA-LIP6-UPMC)
Dans une première partie de cet exposé nous présentons le domaine du Calcul Formel lié à la résolution des systèmes polynomiaux en utilisant les bases de Gröbner. Le calcul de bases de Gröbner (Buchberger) est, en effet, un outil fondamental pour la résolution des systèmes polynomiaux par des techniques algébriques; il est à la base de nombreux solveurs exacts et permet de retrouver toutes les solutions. Nous montrerons aussi quelques grands domaines d’application de ces méthodes où l'usage de méthodes exactes est déterminant. Parmi les applications on distingue le cas discret et le cas continue. Dans le premier cas les solutions sont à rechercher dans un corps fini ; les applications sont alors nombreuses en cryptographie (cryptanalyse algébrique). Dans le deuxième cas les solutions recherchées sont réelles avec des applications dans de nombreux domaines (optimisation globale, robotique, biologie, analyse numérique,).
Dans une deuxième partie nous décrivons brièvement les algorithmes de calcul des bases de Gröbner. L’efficacité des meilleurs algorithmes repose fortement sur des techniques d’algèbre linéaire. Les matrices générées par ces algorithmes sont de grandes tailles (plusieurs millions de lignes et de colonnes) et présentent des propriétés inhabituelles (structure quasi-triangulaires par blocs, creuses, singulières). Il a donc été nécessaire de développer une algorithmique permettant de tirer partie des ces structures. Nous présentons également des librairies d’algèbre linéaire pour architecture multi-cœurs et parallèles. Ces bibliothèques contiennent des algorithmes spécifiques (élimination Gaussienne structurée par exemple) ainsi que des représentations spécifiques des matrices.
Plus d'informations ici
mohab.safey (at) nulllip6.fr
 Mentions légales
Carte du site |