Une solution déterministe au 17e problème de Smale

English

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

25/02/2016 - 09:30 Mr Pierre Lairez Salle 1 - Tour IRMA

Une racine d'un système d'équations polynomiales peut être calculée numériquement par la méthode homotopique: pour résoudre un système F, on part d'un système G dont on connait une racine, et on le déforme progressivement jusqu'à arriver à F tout en faisant suivre la racine à l'aide d'itérations de Newton.  La complexité de cette méthode est bien comprise en terme du conditionnement des systèmes polynomiaux que l'on rencontre le long du chemin de déformation, mais il est difficile de trouver a priori un chemin de déformation efficace.

Shub et Smale ont étudié la complexité en moyenne des méthodes homotopiques, où l'on suppose que le système à résoudre est uniformément distribué dans un certain espace.  Beltrán et Pardo ont décrit un algorithme probabiliste pour calculer une racine approchée d'un système polynomial dont la complexité est polynomiale par rapport à la taille de l'entrée, en moyenne, à la fois par rapport à l'entrée de l'algorithme et sa source d'aléa.  L'objet de l'exposer est de montrer comment supprimer l'aléa dans l'algorithme de Beltràn et Pardo, donnant ainsi un algorithme déterministe de complexité moyenne polynomiale.