Solving determinantal systems using homotopy techniques

02/28/2018
by   Jonathan D. Hauenstein, et al.
0

Let be a field of characteristic zero and be an algebraic closure of . Consider a sequence of polynomialsG=(g_1,...,g_s) in [X_1,...,X_n], a polynomial matrix =[f_i,j] ∈[X_1,...,X_n]^p × q, with p ≤ q,and the algebraic set V_p(F, G) of points in at which all polynomials in and all p-minors of vanish. Such polynomial systems appear naturally in e.g. polynomial optimization, computational geometry.We provide bounds on the number of isolated points in V_p(F, G) depending on the maxima of the degrees in rows (resp. columns) of . Next, we design homotopy algorithms for computing those points. These algorithms take advantage of the determinantal structure of the system defining V_p(F, G). In particular, the algorithms run in time that is polynomial in the bound on the number of isolated points.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset