HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Solving determinantal systems using homotopy techniques

Abstract : Let $\K$ be a field of characteristic zero and $\Kbar$ be an algebraic closure of $\K$. Consider a sequence of polynomials $G=(g_1,\dots,g_s)$ in $\K[X_1,\dots,X_n]$, a polynomial matrix $\F=[f_{i,j}] \in \K[X_1,\dots,X_n]^{p \times q}$, with $p \leq q$, and the algebraic set $V_p(F, G)$ of points in $\KKbar$ at which all polynomials in $\G$ and all $p$-minors of $\F$ 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 $\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.
Document type :
Journal articles
Complete list of metadata

Cited literature [63 references]  Display  Hide  Download

Contributor : Mohab Safey El Din Connect in order to contact the contributor
Submitted on : Wednesday, February 28, 2018 - 9:32:15 AM
Last modification on : Tuesday, January 4, 2022 - 6:29:19 AM
Long-term archiving on: : Monday, May 28, 2018 - 10:04:54 AM


Files produced by the author(s)



Jonathan D. Hauenstein, Mohab Safey El Din, Éric Schost, Thi Xuan Vu. Solving determinantal systems using homotopy techniques. Journal of Symbolic Computation, Elsevier, In press, 104, pp.754-804. ⟨10.1016/j.jsc.2020.09.008⟩. ⟨hal-01719170⟩



Record views


Files downloads