Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Computing critical points for invariant algebraic systems

Abstract : Let $\KK$ be a field and $\phi$, $\f = (f_1, \ldots, f_s)$ in $\KK[x_1, \dots, x_n]$ be multivariate polynomials (with $s < n$) invariant under the action of $\Sc_n$, the group of permutations of $\{1, \dots, n\}$. We consider the problem of computing the points at which $\f$ vanish and the Jacobian matrix associated to $\f, \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 $\Sc_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+d}\choose{d}}$ and $\binom{n}{s+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 \simeq n$ this yields an exponential speed-up with respect to the usual polynomial system solving algorithms.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [42 references]  Display  Hide  Download

https://hal.sorbonne-universite.fr/hal-02927636
Contributor : Mohab Safey El Din <>
Submitted on : Tuesday, September 1, 2020 - 6:37:38 PM
Last modification on : Tuesday, March 23, 2021 - 9:28:03 AM
Long-term archiving on: : Wednesday, December 2, 2020 - 2:52:52 PM

Files

hal-critpoint-main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02927636, version 1
  • ARXIV : 2009.00847

Citation

Jean-Charles Faugère, George Labahn, Mohab Safey El Din, Éric Schost, Thi Xuan Vu. Computing critical points for invariant algebraic systems. 2020. ⟨hal-02927636⟩

Share

Metrics

Record views

252

Files downloads

114