Direction de recherche : Jean-Charles FAUGÈRE

Co-encadrement : TSIGARIDAS Elias

Algorithmes pour les systèmes polynomiaux creux : bases de Gröbner et résultants

La résolution de systèmes polynomiaux est l’un des problèmes les plus anciens et les plus importants en mathématique, et a de nombreuses applications en informatique. C'est un problème intrinsèquement difficile avec une complexité au moins exponentielle en le nombre de variables. Cependant, dans la plupart des cas, les systèmes polynomiaux issus d'applications ont une structure particulière. Dans cette thèse, nous exploitons le caractère creux des polynômes ; c'est-à-dire que nous tirons parti du fait que les polynômes n'ont qu'un petit nombre de termes non nuls. Nous développons des algorithmes pour les systèmes polynomiaux mixtes et creux, c'est-à-dire pour lesquels la structure creuse de chaque polynôme (polytope de Newton) est différente. Nous contribuons dans deux domaines de la théorie de l'élimination : les résultants creux et les bases de Gröbner. Nous travaillons de manière indépendante sur chaque domaine, mais nous les combinons aussi pour introduire de nouveaux algorithmes, établissant pour la première fois un lien entre ces deux domaines dans le contexte creux. Pour cela, nous nous appuyons sur la régularité multigraduée de Castelnuovo-Mumford. Nous utilisons les résultants pour proposer des algorithmes «optimaux» permettant de résoudre des familles de systèmes mixtes multilinéaires et, dans le cas général, nous utilisons les bases de Gröbner pour résoudre les systèmes creux en évitant les calculs inutiles. La complexité de nos algorithmes dépend de la structure creuse des systèmes (polytopes de Newton). Nous proposons également des algorithmes quasi-optimaux pour décomposer les formes binaires.

Publications 2016-2021