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:

*Math/Computer algebra prerequisites*: polynomials, roots, real roots, ...*Semi-algebraic sets and polynomial maps*- Definitions, semi-algebraic sets and real algebraic sets

- Properness, Critical points and critical values

- Transversality theorems

*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

*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.