Solving determinantal systems using homotopy techniques. (May 2021)

• Record Type: Journal Article
• Authors: Hauenstein, Jon D.; Safey El Din, Mohab; Schost, Éric; Vu, Thi Xuan
• Is Part Of: Journal of symbolic computation. Volume 104(2021)
• Page Start: 754
• Page End: 804
• Publication Date: 2021-05
• Subjects: Polynomial system solving -- Homotopy -- Symbolic computation -- Determinantal algebraic sets -- Complexity; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2020.09.008
• Languages: English
• ISSNs: 0747-7171

Abstract

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.