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.
Domains
Symbolic Computation [cs.SC]Origin | Files produced by the author(s) |
---|
Loading...