Newton Polytopes and Witness Sets
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
We present two algorithms that compute the Newton polytope of a polynomial f defining a hypersurface H in n using numerical computation. The first algorithm assumes that we may only compute values of f-this may occur if f is given as a straight-line program, as a determinant, or as an oracle. The second algorithm assumes that H is represented numerically via a witness set. That is, it computes the Newton polytope of H using only the ability to compute numerical representatives of its intersections with lines. Such witness set representations are readily obtained when H is the image of a map or is a discriminant. We use the second algorithm to compute a face of the Newton polytope of the Lroth invariant, as well as its restriction to that face. 2014 Springer Basel.
