Faster real root decision algorithm for symmetric polynomials

DOI10.1145/3597066.3597097arXiv2306.03855OpenAlexW4379933108WikidataQ131124591 ScholiaQ131124591MaRDI QIDQ6081968FDOQ6081968

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)

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$.

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

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Cites Work

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

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)