Short Presentation - PolSys (Polynomial Systems) [the formerly SALSA team]

PolSys is a joint project-team between INRIA, CNRS 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. PolSys 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 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 packages. Algorithms and software developed by PolSys 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 some industrial and academic 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 (action SYNUS in partnership with the group PEQUAN).

Keywords

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.