| Title: |
Computing critical points for invariant algebraic systems |
| Authors: |
Faugère, Jean-Charles; Labahn, George; Safey El Din, Mohab; Schost, Éric; Vu, Thi Xuan |
| Contributors: |
Polynomial Systems (PolSys); LIP6; Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS); Symbolic Computation Group (SCG); David R. Cheriton School of Computer Science; University of Waterloo Waterloo -University of Waterloo Waterloo; ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(2019); ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(2018); ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(2019); European Project: 813211,H2020-MSCA-ITN-2018,H2020-MSCA-ITN-2018,POEMA(2019) |
| Source: |
ISSN: 0747-7171. |
| Publisher Information: |
CCSD; Elsevier |
| Publication Year: |
2023 |
| Subject Terms: |
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] |
| Description: |
International audience ; 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: |
article in journal/newspaper |
| Language: |
English |
| Relation: |
info:eu-repo/semantics/altIdentifier/arxiv/2009.00847; info:eu-repo/grantAgreement//813211/EU/Polynomial Optimization, Efficiency through Moments and Algebra/POEMA; ARXIV: 2009.00847 |
| DOI: |
10.1016/j.jsc.2022.10.002 |
| Availability: |
https://hal.sorbonne-universite.fr/hal-02927636; https://hal.sorbonne-universite.fr/hal-02927636v1/document; https://hal.sorbonne-universite.fr/hal-02927636v1/file/hal-critpoint-main.pdf; https://doi.org/10.1016/j.jsc.2022.10.002 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.91C8626F |
| Database: |
BASE |