Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Homotopy techniques for solving sparse column support determinantal polynomial systems

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download

https://hal.sorbonne-universite.fr/hal-02927630
Contributor : Mohab Safey El Din <>
Submitted on : Tuesday, September 1, 2020 - 6:26:17 PM
Last modification on : Tuesday, March 23, 2021 - 9:28:03 AM
Long-term archiving on: : Wednesday, December 2, 2020 - 2:51:59 PM

Files

hal-column-support-main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02927630, version 1
  • ARXIV : 2009.00844

Citation

George Labahn, Mohab Safey El Din, Éric Schost, Thi Xuan Vu. Homotopy techniques for solving sparse column support determinantal polynomial systems. 2020. ⟨hal-02927630⟩

Share

Metrics

Record views

236

Files downloads

115