Fundamental Algorithms in Real
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
Outline of the class:
Prerequisites: Basic knowledge of computer
algebra (fast arithmetic, gcd computations) and analysis over the reals.
- 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
- 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
- Grobner bases algorithms
Definitions, basic algorithmic problems
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.