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. Algorithms and software developed by the groups are validated by solving challenging applications modeled with non-linear constraints.
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!
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.