Homotopy techniques for solving sparse column support determinantal polynomial systems - Sorbonne Université Accéder directement au contenu
Article Dans Une Revue Journal of Complexity Année : 2021

Homotopy techniques for solving sparse column support determinantal polynomial systems

Mohab Safey El Din
Éric Schost
  • Fonction : Auteur
  • PersonId : 988953
Thi Xuan Vu

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

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 Consultations
163 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More