The PolSys Team - Computer Algebra and Polynomial Systems
Overall description
Our research group focuses on algebraic algorithms for solving mathematical problems in general with a focus on polynomial systems. It is internationally recognized as one of the leading groups in the area of solving systems of polynomial equations/inequalities (non-linear systems) using exact methods (computer algebra).
Our goal is to develop efficient algorithms and software for computing the complex solutions and/or the real ones or in a finite field. We have developed several fundamental algorithms, in particular for computing Gröbner bases and for solving over the reals (real root finding, quantifier elimination, connectivity queries).
Complexity issues are also investigated and recently the group has obtained results for structured polynomial systems (systems with symmetries, overdetermined or bilinear systems, ...) enabling to identify some classes of problems which can be solved in polynomial time.
The practical efficiency of our algorithms relies on highly efficient linear algebra libraries. Hence, the group is involved in the development of parallel high performance linear algebra and Gröbner basis packages for solving polynomial systems. See the msolve library we jointly develop with TU Kaiserslautern. Algorithms and software developed by the groups are validated by solving challenging applications modeled with non-linear constraints.
Campus Pierre et Marie Curie
Sorbonne Université, Paris France
News and upcoming events.
Vincent Neiger received the Distinguished Paper Award, sponsored by SIGSAM/ACM, at ISSAC 2024 for his joint paper with C. Pernet and G. Villard, entitled Computing Krylov iterates in the time of matrix multiplication.Mohab Safey El Din is invited speaker at ICMS 2024
Thi Xuan Vu, former PhD student in our group, is hired as "Maître de Conférences" at the Université de Lille, congratulations!
Rémi Prébet, former PhD student in our group, is hired as "Chargé de recherche" at Inria Lyon, congratulations!
New release v0.6.5 of msolve is available. msolve-news mailing list is here
Focus on applications in robotics
In the old times, we contributed to the study of Stewart platforms through Gröbner bases computations for polynomial system solving.
Nowadays, we do much more complicated things. For instance we are quite proud to be able to analyze automatically the kinematic singularities of some industrial robots. We do that by solving polynomial systems where solving means here counting the number of connected components of the solution set over the reals to some given polynomial system.
We also develop quantifier elimination algorithms which are now used for the stability analysis of sensor-based controlled mechanisms. This range of applications (and the algorithms developed) is pretty new to computer algebra!
Focus on the startup CryptoNext Security and crypto applications
The Cryptonext Security company is a spin-off of our group, funded by Jean-Charles Faugère and Ludovic Perret. Beware, quantum computers may arrive soon and are a threat to standard cryptographic protocols which are used nowadays. Our transfer activity through Cryptonext Security aims at providing new cryptographic solutions which are resistent to quantum computers.
Some of the solutions proposed by Cryptonext Security are based on multivariate polynomial systems and their security is related to the complexity of Gröbner bases.
In particular, the signature scheme called GeMSS is now developed by Cryptonext Security and has been selected for the semi-final of the NIST competition to standardize post-quantum cryptography.
Current application domains
-
Cryptology, in particular algebraic cryptanalysis
Using polynomial system solvers (over finite fields), one can evaluate the security of a cryptosystem. Such a methodology is called algebraic cryptanalysis.
We are proud that two members of the group founded the Cryptonext Security startup, a successful technology transfer initiative! -
Robotics and mechanism design
Non-linear equations arise quite naturally when modeling rigid mechanisms and sensor-based controllers. Our solvers have been used to analyze kinematic singularities of industrial robots (by asnwering connectivity queries in real solution sets to polynomial systems) and for the stability analysis of sensor-based controllers. -
Biology and life sciences
Biological systems are often modeled through dynamical systems with algebraic coefficients. Computing their steady states and equilibria is then of first importance to understand the behaviour of biological systems. Our software have been used to analyze several of such systems. -
Optimization and scientific computing
Our polynomial system solvers can be used to solve a wide range of problems arising in scientific computing or in the applications of scientific computing.
One important area in which we are involved is polynomial optimization and its applications in various areas of engineering sciences (in particular energy consumption).
Our polynomial system solvers have also been used for the stability analysis of numerical schemes or to improve the solving of optimal control solvers. -
Computational geometry
Our polynomial system solvers have been used to solve problems arising in this area of computer science.
One can analyze the shapes of classical objects of computational geometry (such as Voronoi diagrams) which become non-linear in the 3D case. Polynomial system solvers can also be used to solve enumerative problems in computational problems such packing problems. -
Other applications
There are many other applications as non-linear models appear naturally and frequently in many areas. To cite just a few of areas where polynomial systems appear and where we had some contribution, let us mention program verification, quantum physics and information, combinatorics, signal theory and vision.