Homotopy techniques for solving sparse column support determinantal polynomial systems - Sorbonne Université Access content directly
Journal Articles Journal of Complexity Year : 2021

Homotopy techniques for solving sparse column support determinantal polynomial systems

Mohab Safey El Din
Éric Schost
  • Function : Author
  • PersonId : 988953
Thi Xuan Vu

Abstract

Let K be a field of characteristic zero with K its algebraic closure. Given a sequence of polynomials g = (g_1 ,. .. , g_s) ∈ K[x_1 , ... , x_n ] s and a polynomial matrix F = [f_{i,j} ] ∈ K[x_1 , ... , x_n ] p×q , with p ≤ q, we are interested in determining the isolated points of V_p (F , g), the algebraic set of points in K at which all polynomials in g and all p-minors of F vanish, under the assumption n = q − p + s + 1. Such polynomial systems arise in a variety of applications including for example polynomial optimization and computational geometry. We design a randomized sparse homotopy algorithm for computing the isolated points in V_p (F , g) which takes advantage of the determinantal structure of the system defining V_p (F , g). Its complexity is polynomial in the maximum number of isolated solutions to such systems sharing the same sparsity pattern and in some combinatorial quantities attached to the structure of such systems. It is the first algorithm which takes advantage both on the determinantal structure and sparsity of input polynomials. We also derive complexity bounds for the particular but important case where g and the columns of F satisfy weighted degree constraints. Such systems arise naturally in the computation of critical points of maps restricted to algebraic sets when both are invariant by the action of the symmetric group.
Fichier principal
Vignette du fichier
hal-column-support-main.pdf (316.72 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02927630 , version 1 (01-09-2020)

Identifiers

Cite

George Labahn, Mohab Safey El Din, Éric Schost, Thi Xuan Vu. Homotopy techniques for solving sparse column support determinantal polynomial systems. Journal of Complexity, 2021, 66, pp.101557. ⟨10.1016/j.jco.2021.101557⟩. ⟨hal-02927630⟩
286 View
159 Download

Altmetric

Share

Gmail Facebook X LinkedIn More