Newton Polytopes and Witness Sets Academic Article uri icon

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.

published proceedings

  • Mathematics in Computer Science

author list (cited authors)

  • Hauenstein, J. D., & Sottile, F.

citation count

  • 7

complete list of authors

  • Hauenstein, Jonathan D||Sottile, Frank

publication date

  • June 2014