Fundamental Algorithms in Real Algebraic Geometry

Lecturers: Mohab Safey El Din and Jean-Charles Faugère

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
  3. Fast algorithms for real root search to polynomial systems
  4. Grobner bases algorithms
Prerequisites: Basic knowledge of computer algebra (fast arithmetic, gcd computations) and analysis over the reals.