Communications in Information and Systems

Volume 14 (2014)

Number 4

Theoretical aspects of mixed volume computation via mixed subdivision

Pages: 213 – 242

DOI: https://dx.doi.org/10.4310/CIS.2014.v14.n4.a1

Authors

Tianran Chen (Department of Mathematics, Michigan State University, East Lansing, Mich., U.S.A.)

Tien-Yien Li (Department of Mathematics, Michigan State University, East Lansing, Mich., U.S.A.)

Xiaoshen Wang (Department of Mathematics and Statistics, University of Arkansas, Little Rock, Ark., U.S.A.)

Abstract

We analyze the computation of mixed volume of tuples of polytopes via fine mixed subdivisions. This method expresses the mixed volume as a sum of easily computable standard volumes of polytopes called mixed cells. Mixed cells play a critically important role in polyhedral homotopy continuation methods, which in turn are a particularly efficient numerical method for the solution of systems of polynomial equations. We provide a complete and self-contained account of the underlying computational convexity techniques, assuming no background in algebraic geometry.

Full Text (PDF format)

Published 1 April 2015