A polyhedral homotopy algorithm for real zeros (Q6047530)

For a sparse polynomial system consisting of \(n\) polynomials, Bernstein's theorem from 1975 shows that for generic choice of their coefficients, the number of zeros of on \((\mathbb{C})^n\) equals the mixed volume of the \(n\) Newton polytopes. In the early 90s, the polyhedral homotopy method was developed as an algorithmic counterpart of Bernstein's theorem. The main idea is to continuously deform a given polynomial system to another ``easy'' system, that can be solved by pure combinatorics, and then trace back the change in the solution set with numerical path trackers. Viro's patchworking method for complete intersections suggests a map for ``easy'' polynomial systems. The authors design a homotopy continuation algorithm, that is based on Viro's patchworking method, for finding real zeros of sparse polynomial systems. The algorithm is targeted for polynomial systems with coefficients that satisfy certain concavity conditions, it tracks optimal number of solution paths, and it operates entirely over the reals. In more technical terms, they design an algorithm that correctly counts and finds the real zeros of polynomial systems that are located in the unbounded components of the complement of the underlying A-discriminant amoeba. They provide a detailed exposition of connections between Viro's patchworking method, convex geometry of A-discriminant amoeba complements, and computational real algebraic geometry.