Photo Responsable

Team : PolSys - Polynomial Systems

Axes : SSR (👥👥), TMC (👥👥).

Team leader :

Mohab Safey El Din Campus Pierre et Marie Curie 26-00/321

Short presentation

Dessin Bulles HAL Staff directory 1 software

POLSYS/SALSA is a joint team between INRIA and University Pierre and Marie Curie. Our group is internationally recognized as one of the leading group in the area of solving systems of polynomial equations/inequalities (non-linear systems) using exact methods. Our goal is to develop efficient algorithms for computing the complex solutions and/or the real ones or in a finite field. Our group has developed several fundamental algorithms, in particular algorithms for computing Gröbner bases and algorithms based on the so-called critical point method. Complexity issues are also investigated and recently our group has obtained results for structured polynomial systems (systems with symmetries, overdetermined or bilinear systems,…) enabling to identify some classes of problems that can be solved in polynomial time.
The practical efficiency of our algorithms relies on highly efficient linear algebra libraries. Hence, our group is involved in the development of parallel high performance linear algebra packages. Algorithms and software developed by our group are validated by solving challenging applications arising in scientific computing. Beyond the wide range of studied applications, the group focuses on:

  • Applications in Cryptology and, in particular, the emerging topic Algebraic Cryptanalysis. The goal is to evaluate the security of a cryptosystem by reducing its study to the solving of an algebraic system with coefficients in a finite field.
  • Computational Geometry: a new trend in this area is to substitute the manipulation of points and lines with algebraic curves. Intersecting such objects is equivalent to solve an algebraic system.
  • Global optimizations problems of algebraic functions leading to new applications in scientific computing.
  • Software and algorithms developed by the group have been successfully used in several applications fields: Biology, Robotics and Signal Theory.
Our software are devoted to be used in real life applications and teaching. The valorization of this software activity is ensured by their integration in recent releases of the Computer Algebra system Maple (distributed by the WMI Canadian Company)
As a prospective subject, we investigate a new research direction which consists in exploiting interactions between symbolic and numeric computing.

Staff directory

Computer Algebra. Polynomial System Solving. Gröbner Bases. Complexity. Real roots. Parametric systems. Cryptology. Algebraic Cryptanalysis. Algebraic Computational Geometry. Applications. Symbolic/Numeric Interaction. Software. High performance Linear Algebra.

No event planned at present.


Selected publications



Jean-Charles.Faugere (at)