seminario Pierre-Jean Spaenlehauer

Data dell'evento: 
Wed 23/10/2013 ore 11:30

Pierre-Jean Spaenlehauer (MPI Bonn) terrà un seminario
Mercoledì 23 Ottobre alle 11.30 presso la sala conferenze Tricerri del DIMAI su

Complexity bounds for computing critical points with Gröbner bases

Abstract: Let f1,...,fp and q be multivariate polynomials with rational
coefficients. We consider the problem of computing the critical points
of q on the variety V associated to f1,...,fp. Such computations are
central in several algorithms in real algebraic geometry and in
optimization. In practice, Gröbner bases algorithms are efficient
methods to compute these critical points which lie in the
intersection of V and of a determinantal variety defined by the
vanishing of the maximal minors of a Jacobian matrix.

I will present how tools from commutative algebra (the Eagon-Northcott
complex) and from combinatorics (sets of non-intersecting paths)
describe in the generic case the underlying structure of the ideal
vanishing on the critical points and lead to a complexity
analysis of Gröbner basis algorithms for these systems.

In particular, for several families of critical point systems and
under genericity assumptions on the coefficients of the input
polynomials, Gröbner bases can be computed with the F4/F5 algorithms
within a number of arithmetic operations which is polynomial in the
number of complex critical points.

Joint work with Jean-Charles Faugère and Mohab Safey El Din.

sala conferenze Tricerri