Elimination for generic sparse polynomial systems

Abstract

We present a new probabilistic symbolic algorithm that, given a variety defined in an n-dimensional affine space by a generic sparse system with fixed supports, computes the Zariski closure of its projection to an ℓ-dimensional coordinate affine space with ℓ<n. The complexity of the algorithm depends polynomially on some combinatorial invariants associated to the supports.