Solving determinantal systems using homotopy techniques. (May 2021) - Hauenstein, Jon D.; Safey El Din, Mohab; Schost, Éric; Vu, Thi Xuan
Abstract: Let K be a field of characteristic zero and let K ‾ be an algebraic closure of K . Consider a sequence of polynomials G = ( g 1, …, g s ) in K [ X 1, …, X n ] with s < n, a polynomial matrix F = [ f i, j ] ∈ K [ X 1, …, X n ] p × q, with p ≤ q and n = q − p + s + 1, and the algebraic set V p ( F, G ) of points in K ‾ at which all polynomials in G and all p -minors of F vanish. Such polynomial systems appear naturally in polynomial optimization or 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 F and we design probabilistic 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.