Homotopy techniques for solving sparse column support determinantal polynomial systems

DOI10.1016/J.JCO.2021.101557MaRDI QIDQ1979422zbMATH OpenOpenAlexFDO

Authors Mohab Safey El Din, Éric Schost, Thi Xuan Vu, G. Labahn

Publication date 2 September 2021

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.00844

zbMATH Keywords

determinantal systemssparse polynomialssymbolic homotopy

Mathematics Subject Classification ID

Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Solving polynomial systems; resultants (13P15) Numerical computation of determinants (65F40) Symbolic computation and algebraic computation (68W30)

Abstract: Let $mathbfK$ be a field of characteristic zero with $overlinemathbfK$ its algebraic closure. Given a sequence of polynomials $mathbfg=(g_1,ldots,g_s)inmathbfK[x_1,ldots,x_n{]}^s$ and a polynomial matrix $mathbfF=[f_{i,j}]inmathbfK[x_1,ldots,x_n{]}^{pimesq}$, with $pleqq$, we are interested in determining the isolated points of $V_p(mathbfF,mathbfg)$, the algebraic set of points in $overlinemathbfK$ at which all polynomials in $mathbfg$ and all $p$-minors of $mathbfF$ 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(mathbfF,mathbfg)$ which takes advantage of the determinantal structure of the system defining $V_p(mathbfF,mathbfg)$. 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 $mathbfg$ and the columns of $mathbfF$ 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.

Review text

The paper introduces a homotopy continuation method for solving a polynomial system defined by a sequence of sparse polynomials and minors of a matrix. More concretely, given a sequence of polynomials \(\mathbf{g}=(g_1,\ldots,g_s)\) in \(\mathbb{K}[x_1,\ldots,x_n]^s\) and a polynomial matrix \(F=[f_{i,j}]\in \mathbb{K}[x_1,\ldots,x_n]^{p,q}\) with \(p\leq q\), the algorithm computes the isolated points of \(\mathcal{V}_p(F, \mathbf{g})\), the algebraic set of points in \(\mathbb{K}\) at which all polynomials in \(\mathbf{g}\) and all \(p\)-minors of \(F\) vanish, with \( n = q-p + s + 1\). Homotopy methods exploit the structure of the systems to compute their roots, and in this case, the authors take advantage on both the sparsity of the input polynomials and the determinantal structure, as it is shown in Example 6. The principle of homotopy continuation methods is quite simple; it involves constructing a second system defining the same variety which is similar but whose solutions are easy to describe. However, it is highly complicated to achieve good algorithms, with a good algebraic complexity, as it is in this case. That requires the manipulation and the use of symbolic computation and algebraic geometry tools.

Recommendations

• Solving determinantal systems using homotopy techniques
• Numerical stability of path tracing in polyhedral homotopy continuation methods
• Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
• A Polyhedral Method for Solving Sparse Polynomial Systems
• Paramotopy: parameter homotopies in parallel

Cites work

• A baby step-giant step roadmap algorithm for general algebraic sets
• A Gröbner free alternative for polynomial system solving
• A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
• A Polyhedral Method for Solving Sparse Polynomial Systems
• A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set
• Affine solution sets of sparse polynomial systems
• Algorithm 976
• An upper estimate of integral points in real simplices with an application to singularity theory
• Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
• Cell decomposition of almost smooth real algebraic surfaces
• Computing isolated roots of sparse polynomial systems in affine space
• Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology
• Critical point computations on smooth varieties, degree and complexity bounds
• Critical points and Gröbner bases: the unmixed case
• Deformation techniques for efficient polynomial equation solving.
• Deformation techniques for sparse systems
• Deformation techniques to solve generalised Pham systems
• Degeneracy loci and polynomial equation solving
• Elimination for generic sparse polynomial systems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Generalized polar varieties and an efficient real elimination.
• Global optimization of polynomials using generalized critical values and sums of squares
• scientific article; zbMATH DE number 4132308 (Why is no real title available?)
• scientific article; zbMATH DE number 704831 (Why is no real title available?)
• scientific article; zbMATH DE number 1057749 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 939802 (Why is no real title available?)
• scientific article; zbMATH DE number 1424120 (Why is no real title available?)
• Intrinsic complexity estimates in polynomial optimization
• Lower and Upper Bounds for the Number of Lattice Points in a Simplex
• Minimizing polynomials via sum of squares over the gradient ideal
• Newton polytopes and the Bezout theorem
• Numerically computing real points on algebraic sets
• On computing the determinant in small parallel time using a small number of processors
• On the complexity of computing critical points with Gröbner bases
• On the geometry of polar varieties
• Polynomial equation solving by lifting procedures for ramified fibers
• Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set
• Real solving for positive dimensional systems.
• Solving determinantal systems using homotopy techniques
• Solving zero-dimensional systems through the rational univariate representation
• Straight-line programs in geometric elimination theory
• The number of roots of a system of equations
• Using Algebraic Geometry

Cited in

(9)

• Computing critical points for invariant algebraic systems
• Gröbner bases and critical values: the asymptotic combinatorics of determinantal systems
• Solving determinantal systems using homotopy techniques
• Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
• Refined F5 Algorithms for Ideals of Minors of Square Matrices
• Faster real root decision algorithm for symmetric polynomials
• Generic consistency and nondegeneracy of vertically parametrized systems
• Optimized Gröbner basis algorithms for maximal determinantal ideals and critical point computations
• Computing polynomial representation in subrings of multivariate polynomial rings

Describes a project that uses

Uses Software

• Bertini_real
• ISOLATE
• Kronecker
• Bertini

This page was built for publication: Homotopy techniques for solving sparse column support determinantal polynomial systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1979422)