Faster real root decision algorithm for symmetric polynomials

DOI10.1145/3597066.3597097MaRDI QIDQ6081968zbMATH OpenOpenAlexWikidataFDO

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

Publication date 3 November 2023

Published in Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Abstract: In this paper, we consider the problem of deciding the existence of real solutions to a system of polynomial equations having real coefficients, and which are invariant under the action of the symmetric group. We construct and analyze a Monte Carlo probabilistic algorithm which solves this problem, under some regularity assumptions on the input, by taking advantage of the symmetry invariance property. The complexity of our algorithm is polynomial in $d^s,n+dchoosed$, and $nchooses+1$, where $n$ is the number of variables and $d$ is the maximal degree of $s$ input polynomials defining the real algebraic set under study. In particular, this complexity is polynomial in $n$ when $d$ and $s$ are fixed and is equal to $n^{O(1)}{2}^n$ when $d=n$.

Cites work

• scientific article; zbMATH DE number 1349999 (Why is no real title available?)
• scientific article; zbMATH DE number 621806 (Why is no real title available?)
• scientific article; zbMATH DE number 704831 (Why is no real title available?)
• scientific article; zbMATH DE number 2151204 (Why is no real title available?)
• scientific article; zbMATH DE number 3053259 (Why is no real title available?)
• A Gröbner free alternative for polynomial system solving
• A Note on Proper Polynomial Maps
• Algorithms in invariant theory
• Algorithms in real algebraic geometry
• Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
• Bounding the equivariant Betti numbers of symmetric semi-algebraic sets
• Computing critical points for invariant algebraic systems
• Computing cylindrical algebraic decomposition via triangular decomposition
• Critical point computations on smooth varieties, degree and complexity bounds
• Critical points and Gröbner bases: the unmixed case
• Cylindrical algebraic decomposition using local projections
• Cylindrical algebraic decomposition using validated numerics
• Cylindrical algebraic decomposition with equational constraints
• Degeneracy loci and polynomial equation solving
• Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets
• Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
• Generalized polar varieties and an efficient real elimination.
• Generalized polar varieties: geometry and algorithms
• Homotopy techniques for solving sparse column support determinantal polynomial systems
• Intrinsic complexity estimates in polynomial optimization
• On the Theoretical and Practical Complexity of the Existential Theory of Reals
• On the bit complexity of finding points in connected components of a smooth real hypersurface
• On the combinatorial and algebraic complexity of quantifier elimination
• On the complexity of computing critical points with Gröbner bases
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• On the degree and half-degree principle for symmetric polynomials
• On the intrinsic complexity of point finding in real singular hypersurfaces
• On the positivity of symmetric polynomial functions. I: General results
• Polar varieties and efficient real elimination
• Polar varieties, real equation solving, and data structures: the hypersurface case
• Real quantifier elimination is doubly exponential
• Real root finding for equivariant semi-algebraic systems
• Resultant of an equivariant polynomial system with respect to the symmetric group
• Solving a system of algebraic equations with symmetries
• Solving determinantal systems using homotopy techniques
• Solving polynomial systems globally invariant under an action of the symmetric group and application to the equilibria of N vortices in the plane
• Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases
• Solving systems of polynomial inequalities in subexponential time
• Symmetric semi-algebraic sets and non-negativity of symmetric polynomials
• Symmetry groups, semidefinite programs, and sums of squares
• The complexity of quantifier elimination and cylindrical algebraic decomposition
• Triangular decomposition of semi-algebraic systems
• Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets

This page was built for publication: Faster real root decision algorithm for symmetric polynomials

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