Computing Critical Points for Algebraic Systems Defined by Hyperoctahedral Invariant Polynomials

Let K be a field of characteristic zero and K[x(1), . . . , x(n)] the corresponding multivariate polynomial ring. Given a sequence of s polynomials f = (f(1), . . . , f(s)) and a polynomial phi, all in K[x(1), . . . , x(n)] with s < n, we consider the problem of computing the set W (phi, f) of points at which f vanishes and the Jacobian matrix of f, phi with respect to x(1), . . . , 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 hyperoctahedral representation to describe B-n-invariant sets. We study the invariance properties of the input polynomials to split W (phi, f) according to the orbits of B-n and then design an algorithm whose output is a hyperoctahedral representation of W (phi, f). The runtime of our algorithm is polynomial in the total number of points described by the output.