Polynomial system solving over the reals has many applications in engineering sciences such as robotics, mechanics, biology or control theory. It has also strong connections with fundamental problems arising in algebraic complexity and computer arithmetics.
The goal of this course is to provide some knowledge on fundamental algorithms for solving polynomial systems over the reals. The course covers basic questions such as deciding the existence of real roots to polynomial systems, or compute sample points in each connected component of the real solution set. Basic algorithms for this task make intensive use of algebraic elimination algorithms such as Grobner bases algorithms which will be studied.

The course will focus on fundamental algorithms designed during the past decade which have an asymptotically optimal complexity and whose practical behaviours reflect the complexity gains (compared to previous approaches).

Outline of the class:

1. Math/Computer algebra prerequisites: polynomials, roots, real roots, ...
2. Semi-algebraic sets and polynomial maps
   Definitions, semi-algebraic sets and real algebraic sets
   Properness, Critical points and critical values
   Transversality theorems
3. Fast algorithms for real root search to polynomial systems
   Advanced properties of proper maps and polar varieties
   Degree bounds and algebraic modeling
   Algorithm design: generic cases
   Algorithm design: singular cases
   Applications
4. Grobner bases algorithms
   Definitions, basic algorithmic problems
   Algorithm F4
   Algorithm F5
   hilbert series / complexity analysis
   Application to structured systems

• Ideals, Varieties and Algorithms, Cox, Little, O'Shea, Springer.
• Introduction à la résolution des systèmes polynomiaux
• Efficient algorithms in real algebraic geoemtry, M. Safey El Din, CNRS Editions (also in french)
• Algorithms in real algebraic geometry, S. Basu, M.-F. Roy, R. Pollack, Springer.