On the complexity of computing critical points with Gröbner bases
Vortrag von Dr. Pierre-Jean Spaenlehauer
Datum: 08.12.14 Zeit: 11.00 - 12.00 Raum: UNINE, B217
Computing the critical points of a polynomial function q(X1,..., Xn) restricted to an algebraic set f1(X1,...,Xn) = ... = fp(X1,...,Xn) = 0 is a problem arising in several applications (optimization, real algebraic geometry, etc.). In this talk, we focus on Gröbner bases algorithms for the computation of an exact algebraic description of these critical points. These points can be defined as the solutions of a highly structured polynomial system, involving minors of a Jacobian matrix. By using tools from commutative algebra (Eagon-Northcott complex, quasi-homogeneous rings, Hilbert series), we show that this algebraic structure yields complexity bounds for the Gröbner basis computation which match the best known bounds for this problem. In particular, if all the input polynomials q, f1,..., fn share the same degree D and have generic coefficients, then the arithmetic complexity is bounded D^{O(n)}, which is polynomial in the number of critical points in the algebraic closure. When the input polynomials do not share the same degree, then we derive finer complexity bounds which depend on the list of degrees of the input polynomials and on the number of critical points in the algebraic closure.Joint work with Jean-Charles Faugère and Mohab Safey El Din.