DECOMPASS - Systèmes polynomiaux décomposables : algorithmes et applications->

Coordinateur : Vu Thi Xuan, université de Lille, CRIStAL

Équipe : CFHP du Groupe Thématique : CO2.

Dates : 2027 - 2031

Résumé :

La résolution de systèmes polynomiaux se trouve au cœur de la géométrie algébrique effective, avec des applications majeures en optimisation, en géométrie algébrique réelle et en cryptographie. Cependant, ces problèmes sont souvent difficiles d’un point de vue calculatoire (beaucoup sont NP-durs) en raison de l’explosion combinatoire et du phénomène de croissance intermédiaire des expressions dans les calculs symboliques.

Le projet DECOMPASS (Systèmes polynomiaux décomposables : algorithmes et applications) vise à surmonter ces limitations en exploitant les structures de composition cachées dans les systèmes polynomiaux multivariés. L’idée centrale est que, lorsqu’un polynôme ou un système peut être exprimé comme une composition de systèmes plus simples, il devient possible de réduire la dimension effective et la complexité algébrique du problème, ce qui conduit à des stratégies de résolution beaucoup plus efficaces.

Le projet aborde à la fois des défis théoriques et pratiques : il développera de nouvelles méthodes pour détecter la décomposabilité, calculer des décompositions explicites, et résoudre efficacement des systèmes polynomiaux multivariés décomposables. La démarche principale combine des techniques symboliques et numériques, avec une attention particulière portée aux méthodes de continuation par homotopie, afin de concevoir à la fois des algorithmes symboliques et des algorithmes hybrides symboliques-numériques pour trouver un compromis entre l’exactitude des calculs algébriques et la nécessité de passer à l’échelle.

Les résultats attendus incluent de nouvelles perspectives théoriques sur la structure et la complexité des systèmes polynomiaux décomposables, une nouvelle génération d’algorithmes efficaces pour la résolution de systèmes multivariés, des implémentations logicielles en open source, et des avancées concrètes dans des applications telles que l’optimisation polynomiale globale et la cryptographie multivariée.

Abstract :

Polynomial system solving lies at the heart of computational algebraic geometry, with major applications in optimization, real algebraic geometry, and cryptography. However, these problems are often computationally intractable (many are NP-hard) due to combinatorial explosion and the phenomenon of intermediate expression swell in symbolic computations.

The DECOMPASS project (Decomposable Polynomial Systems : Algorithms ans Applications) aims to address these limitations by exploiting hidden compositional structures in multivariate polynomial systems. The central idea is that when a polynomial or a system can be expressed as a composition of simpler maps, it becomes possible to reduce the effective dimension and algebraic complexity of the problem, leading to significantly more efficient solution strategies.

The project addresses both foundational and practical challenges : it will develop new methods to detect decomposability, compute explicit decompositions, and solve decomposable multivariate polynomial systems efficiently. The main approach combines symbolic and numerical techniques, with a particular focus on homotopy continuation methods, to design both symbolic algorithms and hybrid symbolic-numeric algorithms that balance algebraic exactness with computational scalability.

Expected outcomes include new theoretical insights into the structure and complexity of decomposable polynomial systems, a new generation of efficient algorithms for multivariate system solving, open-source software implementations, and concrete advances in applications such as global polynomial optimization and multivariate cryptography.