New trends in algorithms for real algebraic geometry
November 23--27 2009
PresentationAlgorithms in real algebraic geomety enjoy currently a quick development in various directions.
aim of the seminar is to introduce the participants to a variety
of newly developed methods for algorithms in real algebraic
geometry, linking the topic to several other fields of pure and applied
The lecturers will base their talks on available
documents: survey papers, recent publications and will make every
effort to be accessible to non specialists.
Saugata Basu, (Purdue), "Algorithmic semialgebraic topology"
these lectures, we will describe quantitative results on the
topological complexity of semi-algebraic sets, as well as
efficient algorithms for computing topological invariants of
semi-algebraic sets (such as the number of connected components, the
Euler-Poincar\'e characteristic, all Betti numbers etc).
We will develop the necessary tools from algebraic topology (such as simplicial homology theory,
Mayer-Vietoris sequence, spectral sequences etc.) as part of the course.
We will also discuss extensions of the quantitative results to the more general setting of o-minimal structures.
we will discuss applications in discrete and computational geometry, as
well as in computational complexity theory.
Monique Laurent, (CWI, Amsterdam), "Sums of squares, moment matrices and optimization over polynomials"
Polynomial optimization deals with minimizing a multivariate polynomial over a basic closed semi-algebraic set.
easy to solve when all polynomials are linear (via linear programming),
the problem becomes hard as soon as it involves non-linear polynomials.
A natural approach is to relax the problem and to consider
easier to solve, convex relaxations. The basic idea, which goes
back to work of Hilbert, is to relax non-negative polynomials by sums
of squares of polynomials, a notion which can be tested efficiently
(using semidefinite programming algorithms). On the dual side, one
views points as (atomic) measures and one searches for efficient
conditions characterizing sequences of moments of non-negative measures
on the semi-algebraic set.
We will present these hierarchies of
approximations and their main properties: asymptotic/finite
convergence, optimality certificate, and extraction of global optimum
solutions, and illustrate the method on several problem classes.
The main mathematical tools underlying these properties will be reviewed: In particular,
(1) results from real algebraic geometry about sums of squares representations for positive polynomials,
(2) results from moment theory dealing with atomic measures and finite rank moment matrices,
(3) results from commutative algebra for solving systems of polynomial equations.
Marie-Francoise Roy, (Rennes), "Certificates of positivity"
A certificate of positivity is an algebraic expression proving that a given polynomial P is positive. For example, writing P as a sum of squares is a certificate of positivity for P.
proved that every positive polynomials is a sum of squares, giving thus
a positive answer to Hilbert 17-th problem. His proof, based on Zorn's
lemma, is highly non constructive and finding explicitly the sum of
squares is a very difficult task. The method we use consists in proving
algorithmically that the set where the polynomial is negative is empty,
and transforming this algorithmic proof into an algebraic identity. We
shall present what is currently known on effective Hilbert 17-th
problem, insisting on the fact that the methods are valid in a general
real closed field and provide uniform bounds (the degrees in the output
do not depend on the bitsize of the input coefficients, but only in the
degree and number of variables).
Other certificates of
positivity (on the positive orthant, or on the simplex) are based on
results by Polya and Bernstein. Berstein polynomials, for example, are
positive on the simplex, and a positive combination of them is positive
as well. A partial reciprocal is true, by ncreasing the degree of
the Bernstein, or by subdividing the simplex. This gives two different
kinds of certificates, the approach by subdivision being much more
These certificates are not uniform, since the size of the
certificate output depends on the bitsize of the coefficients, and Polya and Bernstein results are not
valid in a general real closed field.
Frank Sottile, (Texas A&M), "Numerical real algebraic geometry"
homotopy continuation gives efficient and naturally parallel algorithms
to find all complex solutions to a system of polynomial
equations. The real solutions are obtained by sifting the complex
solutions, selecting those with small imaginary part.
In contrast, the Khovanskii-Rolle algorithm is a different numerical continuation algorithm that only
real solutions and is naturally parallel. This new continuation
algorithm is based on the proof of the current best bounds for the
number of real solutions to a system of sparse polynomial equations,
including the gale dual transformation of polynomial systems.
lectures will discuss numerical homotopy continuation, Gale duality,
the new fewnomial bounds, and then present the Khovanskii-Roll
continuation algorithm. Augmenting the lectures will be computer
exercises, challenges, and open problems.
Organization16 hours of lectures (four hours per lecturer)
Problem sessions will be organized
Mini-projects (some including the use of software) will be proposed
Note that Oberwolfachsseminars are for young researchers (pre- and post-doc)
Deadline 15 October
Apply directly to Oberwolfach (go to http://www.mfo.de/ and then choose Oberwolfach Seminars in the left menu).