Let $\mathbb{ K}$ be a field of characteristic zero and $\mathbb{ K}[x_1, \dots, x_n]$ the corresponding multivariate polynomial ring. Given a sequence of $s$ polynomials $\mathbf{ f} = (f_1, \dots, f_s)$ and a polynomial $\phi$, all in $\mathbb{ K}[x_1, \dots, x_n]$ with $s<n$, we consider the problem of computing the set $W(\phi, \mathbf{ f})$ of points at which $\mathbf{ f}$ vanishes and the Jacobian matrix of $\mathbf{ f}, \phi$ with respect to $x_1, \dots, x_n$ does not have full rank. This problem plays an essential role in many application areas. In this paper we focus on a case where the polynomials are all invariant under the action of the signed symmetric group $B_n$. We introduce a notion called { \em hyperoctahedral representation} to describe $B_n$-invariant sets. We study the invariance properties of the input polynomials to split $W(\phi, \mathbf{ f})$ according to the orbits of $B_n$ and then design an algorithm whose output is a { hyperoctahedral representation} of $W(\phi, \mathbf{ f})$. The runtime of our algorithm is polynomial in the total number of points described by the output.
Categories: cs.SC