07/03/2014

Intervenant(s) : Simone Naldi (LAAS/CNRS, Toulouse and LIP6, Université Paris 6)

We study algebraic varieties defined by rank constraints on square matrices whose entries are linear forms with rational coefficients. Our main contribution is the construction of efficient exact algorithms for finding real points in every connected component of these determinantal varieties. Using standard results, this problem can be solved with algorithms whose complexity is exponential in the number of variables. Solving it in a better complexity class, taking advantage of the geometric structure of the problem, is required in many scientific areas, like convex optimization or convex algebraic geometry. We present a new exact algorithm for the case of the hypersurface defined by the determinant of a linear matrix: its complexity is polynomial in the number of variables, if the size of the matrix is fixed. We also give some details about the generalization to higher rank defects.

This is a joint work with Didier Henrion and Mohab Safey El Din.

Elias.Tsigaridas (at) nulllip6.fr