Abstract: We present two algorithms that compute the Newton polytope of a polynomial defining a hypersurface H in C^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 L"uroth invariant, as well as its restriction to that face.
Recommendations
Cites work
- scientific article; zbMATH DE number 3834108 (Why is no real title available?)
- scientific article; zbMATH DE number 2079841 (Why is no real title available?)
- scientific article; zbMATH DE number 5245181 (Why is no real title available?)
- An Algorithm for Convex Polytopes
- An explicit expression of the Lüroth invariant
- Classical algebraic geometry. A modern view
- Computing the Newton polygon of the implicit equation
- Computing the multiplicity structure in solving polynomial systems
- Computing tropical resultants
- Deflation algorithm for the multiple roots of a system of nonlinear equations
- Elimination theory and Newton polytopes
- Elimination theory for tropical varieties
- Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
- Isosingular sets and deflation
- Membership tests for images of algebraic sets by linear projections
- Modified deflation algorithm for the solution of singular problems. I. A system of nonlinear algebraic equations
- Newton polyhedra of discriminants of projections
- Newton's method with deflation for isolated singularities of polynomial systems
- Polyhedral end games for polynomial continuation
- Quartic curves and their bitangents
- Recovering exact results from inexact numerical data in algebraic geometry
- Software for numerical algebraic geometry: a paradigm and progress towards its implementation
- The Logarithmic Limit-Set of an Algebraic Variety
- The Newton polytope of the implicit equation
- The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
- Tropical Implicitization and Mixed Fiber Polytopes
- Witness sets of projections
- iB4e: a software framework for parametrizing specialized LP problems
Cited in
(15)- Computing Tropical Curves via Homotopy Continuation
- Binomiality testing and computing sparse polynomials via witness sets
- Numerical software to compute Newton polytopes
- Numerical software to compute Newton polytopes and tropical membership
- Evaluating and differentiating a polynomial using a pseudo-witness set
- Witness sets of projections
- Computation and applications of the Newton polyhedrons
- Computing complex and real tropical curves using monodromy
- Rational parametrizations, intersection theory, and Newton polytopes
- Pruning algorithms for pretropisms of Newton polytopes
- Elimination theory and Newton polytopes
- The Newton polytope of the implicit equation
- Signatures of algebraic curves via numerical algebraic geometry
- Hilbert polynomials for finitary matroids
- Polyhedral methods in numerical algebraic geometry
This page was built for publication: Newton polytopes and witness sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q475408)
