Polynômes Hyperboliques : Algorithmes, Complexité, Implantations – HYPERSPACE

Un polynôme réel en une variable est hyperbolique si toutes ses racines sont réelles, ou de manière équivalente, s’il peut s’écrire comme le polynôme caractéristique d’une matrice symétrique. Tester efficacement cette propriété, qui peut s’étendre au cas en plusieurs variables, est un problème ouvert de l’informatique-mathématique. Si d’une part les polynômes hyperboliques constituent maintenant un domaine d’intérêt central dans les applications, de l’autre, les aspects de calcul ou de complexité ont pour le moment un rôle marginal dans cette théorie. Le but du projet HYPERSPACE est de développer une approche effective. D’une part, nous proposons d’améliorer les algorithmes existants pour le calcul de représentations déterminantales (un certificat d’hyperbolicité qui existe dans des cas spécifiques) ou indépendants des représentations classiques. De l'autre, le projet sera consacré à l’implantation d'algorithmes efficaces dans une nouvelle bibliothèque dédiée aux polynômes hyperboliques.