2020/09/02 by Faugère, Jean-Charles, George Labahn, Mohab Safey El Din +6 · 1 citation
Computer Science · Mathematics · #Advanced Differential Equations and Dynamical Systems #Commutative Algebra and Its Applications #FOS: Computer and information sciences #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · doi:10.48550/arxiv.2009.00847
openalex publication_date 2020/09/02 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Let K be a field and ϕ, f = (f1, …, fs) in K[x1, …, xn] be multivariate polynomials (with s < n) invariant under the action of Sn, the group of permutations of \1, …, n\. We consider the problem of computing the points at which f vanish and the Jacobian matrix associated to f, ϕ 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 Sn. This allows us to design an algorithm which gives a triangular description of the solution space and which runs in time polynomial in ds, n+d\choosed and \binomns+1 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 d ≃ n this yields an exponential speed-up with respect to the usual polynomial system solving algorithms.