Fall 2014

On the Critical Point Method and Deciding Connectivity Queries in Real Algebraic Sets: From Theory to Practice

Wednesday, October 15th, 2014 9:00 am10:00 am

Add to Calendar


Calvin Lab Auditorium

Critical point methods are at the core of the interplay between polynomial optimization and polynomial system solving over the reals. These methods are used in algorithms for solving various problems such as deciding the existence of real solutions of polynomial systems, performing one-block real quantifier elimination, answering connectivity queries in semi-algebraic sets, etc.

The input consists of $s$ polynomials in $n$ variables of degree at most $D$. Usually, the complexity of the algorithms is $(s\, D)^{O(n^\alpha)}$ where $\alpha$ is a constant. In the past decade, tremendous efforts have been deployed to improve the exponents in the complexity bounds. This led to efficient implementations and new geometric procedures for solving polynomial systems over the reals that exploit properties of critical points and the so-called polar varieties.

In the first part of this talk, we present an overview of these techniques and their impact on practical algorithms. In the second part, we show how we can exploit algebraic and geometric properties of polar varieties to improve roadmap algorithms for deciding connectivity queries. In particular, we present an algorithm, obtained with E. Schost, that computes roadmaps in smooth bounded real algebraic sets in time which is essentially $O( (s\, D)^{6(n\log(n))})$. This complexity is subquadratic in the output size and a first implementation shows that it can already solve problems that are out of reach of previous approaches.