Calcul de points critiques par les bases de Gröbner : complexité et application aux problèmes de minimisation.

On considère l'ensemble des solutions réelles V d'un système S d'équations polynomiales de même degré et une application linéaire restreinte à V. Le calcul de points critiques de telles applications joue un rôle essentiel dans divers algorithmes permettant d'étudier les solutions réelles de systèmes d'équations et/ou dans des problèmes de minimisation. Sous des hypothèses de généricité sur S, les points critiques sont définis par l'annulation des équations de S et des mineurs maximaux d'une matrice jacobienne. Ces systèmes sont donc fortement structurés. On observe en pratique que, sur de tels systèmes, le calcul de bases de Gröbner a un comportement spécifique. Dans cet exposé, nous donnons sous des hypothèses de généricité une forme explicite de la série de Hilbert et du degré de régularité de l'idéal s'annulant sur les points critiques. Cela conduit à une analyse de la complexité du calcul de bases de Gröbner. Nous montrons que le nombre d'opérations arithmétiques est polynomial en le nombre de solutions complexes. En particulier, dans le cas où le système S est quadratique et la codimension de V est fixée, le nombre d'opérations arithmétiques est polynomial en le nombre de variables. Travail commun avec Jean-Charles Faugère et Mohab Safey El Din.