Polyno^mes et Applications via Calculs Efficaces – PeACE

L'algèbre linéaire est probablement l'outil mathématique le plus utilisé pour modéliser des phénomènes et résoudre effectivement (algorithmiquement) des problèmes. Classiquement, pour traiter des objets non linéaires, nous (essayons de) les linéariser. Cependant, au cours des dernières décennies et grâce à la disponibilité d'ordinateurs plus rapides, les systèmes d'équations polynomiales ont commencé à être utilisés comme une alternative à cette approche. Les systèmes polynomiaux sont plus expressifs que les systèmes linéaires, mais ils sont aussi beaucoup plus difficiles à calculer. D'un point de vue pratique, il est essentiel de comprendre ce compromis ; nous voulons utiliser des modèles puissants, mais seulement s'ils nous permettent de résoudre concrètement (et efficacement) des problèmes. L'objectif de ce projet va dans ce sens : Nous développerons et mettrons en œuvre des algorithmes spécialisés pour les systèmes d'équations polynomiales provenant d'applications. Notre stratégie est de nous concentrer sur l'exploitation des structures de sparsité des problèmes d'intérêt afin d'améliorer les approches générales connues d'un point de vue pratique et théorique.

PeACE se centre sur le paradigme symbolique des calculs algébriques. Cela signifie que nous manipulons les entrées exactement plutôt que de travailler avec des approximations, ce qui est particulièrement utile pour explorer de nouvelles façons d'exploiter la structure et de traiter les situations dégénérées qui surviennent dans ces systèmes. Nos principaux outils de calcul sont les bases de Gröbner et les résultantes. Notre objectif est d'améliorer les algorithmes de pointe pour calculer ces outils en exploitant les structures de sparsité. Nous appliquerons ces améliorations dans le contexte de l'analyse des données topologiques.