Real root finding for equivariant semi-algebraic systems

DOI10.1145/3208976.3209023MaRDI QIDQ5120214zbMATH OpenOpenAlexWikidataFDO

Authors Cordian Riener, Mohab Safey El Din

Publication date 9 September 2020

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

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

zbMATH Keywords

polynomial system solvingsemi-algebraic setssymmetric group

Mathematics Subject Classification ID

Semialgebraic sets and related spaces (14P10) Numerical computation of roots of polynomial equations (65H04) Nonnumerical algorithms (68W05)

Abstract: Let $R$ be a real closed field. We consider basic semi-algebraic sets defined by $n$-variate equations/inequalities of $s$ symmetric polynomials and an equivariant family of polynomials, all of them of degree bounded by $2d<n$. Such a semi-algebraic set is invariant by the action of the symmetric group. We show that such a set is either empty or it contains a point with at most $2d-1$ distinct coordinates. Combining this geometric result with efficient algorithms for real root finding (based on the critical point method), one can decide the emptiness of basic semi-algebraic sets defined by $s$ polynomials of degree $d$ in time $(sn{)}^{O(d)}$. This improves the state-of-the-art which is exponential in $n$. When the variables $x_1,ldots,x_n$ are quantified and the coefficients of the input system depend on parameters $y_1,ldots,y_t$, one also demonstrates that the corresponding one-block quantifier elimination problem can be solved in time $(sn{)}^{O(dt)}$.

Recommendations

• On the equivariant Betti numbers of symmetric definable sets: vanishing, bounds and algorithms
• Computing real radicals and S-radicals of polynomial systems
• Bounding the equivariant Betti numbers of symmetric semi-algebraic sets
• Some speed-ups and speed limits for real algebraic geometry
• scientific article; zbMATH DE number 3870491

Cited in

(9)

• Multivariate interpolation: preserving and exploiting symmetry
• Computing critical points for invariant algebraic systems
• Cooperativity, absolute interaction, and algebraic optimization
• Symmetry in multivariate ideal interpolation
• scientific article; zbMATH DE number 3870491 (Why is no real title available?)
• Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients
• Faster real root decision algorithm for symmetric polynomials
• The poset of Specht ideals for hyperoctahedral groups
• Deciding connectivity in symmetric semi-algebraic sets

This page was built for publication: Real root finding for equivariant semi-algebraic systems

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