Team presentation

The SPACES research project aims to designing and implementing algorithms for solving polynomial systems with coefficients in the field of the rationals or in a finite field, and whose dimension is either zero (finite number of solutions in an algebraic closure or in the complex field) or positive (infinite number of solutions).

Among the fields of applications in which some results have already been obtained, we can point out simulation, control and diagnostic of parallel manipulators, celestial mechanics, cryptography (in the case of finite fields), image compression and biophysics. An aim of the team is to extend significatively this list of fields of applications.

The ``resolution’’ of such systems consists in giving an accurate description of the set of solutions which is well-suited to the needs of the user. In the case of polynomial systems of dimension zero, this description is currently a numerical approximation of the solutions lying in a field (real, or complex numbers), with a good control on the accuracy. In the general case, the ultimate objective is to describe completely the topology of the set of solutions. The computation of such a description being nowadays untractable, our priority is to determine intermediate classes of problems or questions which are practically solvable and useful to applications.

Since their complexity is at least exponential, solving such problems needs to improve the algorithms, but also to use efficient technics of implementation and to develop suitable arithmetics (multi-precision integers and floats, intervalls, and polynomials, algebraic infinitesimals, etc.).

Research themes

• Algebraic solving
• Real solutions
• Arithmetics
• Hybrid methods

An important task of our team consists in developing efficient softwares to solve algebraic problems.

International and industrial relations

• ACI Cryptology ``PolyCrypt’’
• Cooperation with the Magma group de l’University of Sydney