Computing critical points for invariant algebraic systems

DOI10.1016/J.JSC.2022.10.002MaRDI QIDQ2100065zbMATH OpenOpenAlexFDO

Authors Jean-Charles Faugère, Mohab Safey El Din, Éric Schost, Thi Xuan Vu, G. Labahn

Publication date 21 November 2022

Published in Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitycritical pointsdeterminantal systemsinvariant algebraic systemspolynomial systems solving

Mathematics Subject Classification ID

Actions of groups on commutative rings; invariant theory (13A50) Computational aspects of higher-dimensional varieties (14Q15)

Abstract: Let $mathbfK$ be a field and $phi$, $mathbff=(f_1,ldots,f_s)$ in $mathbfK[x_1,dots,x_n]$ be multivariate polynomials (with $s<n$) invariant under the action of $mathcal{S}_n$, the group of permutations of $1,dots,n$. We consider the problem of computing the points at which $mathbff$ vanish and the Jacobian matrix associated to $mathbff,phi$ is rank deficient provided that this set is finite. We exploit the invariance properties of the input to split the solution space according to the orbits of $mathcal{S}_n$. This allows us to design an algorithm which gives a triangular description of the solution space and which runs in time polynomial in $d^s$, $n+dchoosed$ and $$ where $d$ is the maximum degree of the input polynomials. When $d,s$ are fixed, this is polynomial in $n$ while when $s$ is fixed and $dsimeqn$ this yields an exponential speed-up with respect to the usual polynomial system solving algorithms.

Recommendations

• Solving a system of algebraic equations with symmetries
• scientific article; zbMATH DE number 1741032
• Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases
• Critical points and Gröbner bases: the unmixed case
• Critical point computations on smooth varieties, degree and complexity bounds

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 probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set
• Affine solution sets of sparse polynomial systems
• Algebraic degree of polynomial optimization
• Algorithm 976
• 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
• Cell decomposition of almost smooth real algebraic surfaces
• Computation of invariants of finite abelian groups
• Computational invariant theory
• Computing isolated roots of sparse polynomial systems in affine space
• Critical points and Gröbner bases: the unmixed case
• Deformation techniques for efficient polynomial equation solving.
• Deformation techniques for sparse systems
• Elimination for generic sparse polynomial systems
• Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
• Fast multivariate power series multiplication in characteristic zero
• FGb: A Library for Computing Gröbner Bases
• Global optimization of polynomials using generalized critical values and sums of squares
• Gröbner bases of symmetric ideals
• Homotopy techniques for solving sparse column support determinantal polynomial systems
• scientific article; zbMATH DE number 4132308 (Why is no real title available?)
• scientific article; zbMATH DE number 1264799 (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 1181673 (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?)
• Ideals defined by matrices and a certain complex associated with them
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Intrinsic complexity estimates in polynomial optimization
• Invariant algebraic sets and symmetrization of polynomial systems
• Minimizing polynomials via sum of squares over the gradient ideal
• Numerically computing real points on algebraic sets
• On the complexity of computing critical points with Gröbner bases
• On the complexity of computing with zero-dimensional triangular sets
• On the complexity of symmetric polynomials
• On the degree and half-degree principle for symmetric polynomials
• On the geometry of polar varieties
• On the positivity of symmetric polynomial functions. I: General results
• Polynomial equation solving by lifting procedures for ramified fibers
• Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set
• Real root finding for equivariant semi-algebraic systems
• Real solving for positive dimensional 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 zero-dimensional systems through the rational univariate representation
• Straight-line programs in geometric elimination theory
• Symmetric ideals, Specht polynomials and solutions to symmetric systems of equations
• Symmetric semi-algebraic sets and non-negativity of symmetric polynomials
• The membrane inclusions curvature equations

Cited in

(11)

• Solving a system of algebraic equations with symmetries
• Computation of invariant curves and identifying the type of critical point
• Extrema of Landau polynomials
• Faster real root decision algorithm for symmetric polynomials
• The poset of Specht ideals for hyperoctahedral groups
• Linear slices of hyperbolic polynomials and positivity of symmetric polynomial functions
• Additive and multiplicative coinvariant spaces of Weyl groups in the light of harmonics and graded transfer
• Symmetries in polynomial optimization
• Connectivity in symmetric semi-algebraic sets
• Computing polynomial representation in subrings of multivariate polynomial rings
• Deciding connectivity in symmetric semi-algebraic sets

Describes a project that uses

Uses Software

• Kronecker
• FGb
• ISOLATE
• Bertini_real

This page was built for publication: Computing critical points for invariant algebraic systems

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