Solving determinantal systems using homotopy techniques

2018/02/28 by Hauenstein, Jonathan D., Din, Mohab Safey El, Schost, Éric +1
#FOS: Computer and information sciences #Symbolic Computation (cs.SC)

paper · doi:10.48550/arxiv.1802.10409

Abstract

Let \K be a field of characteristic zero and \Kbar be an algebraic closure of \K. Consider a sequence of polynomialsG=(g_1,…,g_s) in \K[X_1,…,X_n], a polynomial matrix \F=[f_i,j] ∈ \K[X_1,…,X_n]^{p × q}, with p ≤ q,and the algebraic set V_p(F, G) of points in \KKbar at which all polynomials in \G and all p-minors of \Fvanish. 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 \F. 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.

Related

• Homotopy techniques for solving sparse column support determinantal polynomial systems
• Polynomial Homotopies for Dense, Sparse and Determinantal Systems
• Solving Degenerate Sparse Polynomial Systems Faster
• Computing critical points for invariant algebraic systems
• Gröbner bases and critical values: The asymptotic combinatorics of determinantal systems