Why polyhedra matter in non-linear equation solving
J. Maurice Rojas · Contemporary mathematics - American Mathematical Society · 2003
We give an elementary introduction to some recent polyhedral techniques for understanding and solving systems of multivariate polynomial equations. We provide numerous concrete examples and assume no background in algebraic geometry. Highlights include the following: (1) A completely self-contained proof of an extension of Bernstein’s Theorem. Our extension relates volumes of polytopes with the number of connected components of the complex zero set of a polynomial system, and allows any number of polynomials and/or variables. (2) A near optimal complexity bound for computing mixed area — a quantity intimately related to counting complex roots in the plane. (3) Illustration of the connection between polyhedral methods, amoeba theory, toric varieties, and discriminants. We thus cover most of the theory preceding polyhedral homotopy and toric (a.k.a. sparse) resultant-based methods for solving systems of multivariate polynomial equations