Fall 2014

Mixed Volume Computation in (another) Mixed Volume Time

Thursday, October 16th, 2014 11:35 am12:00 pm

Add to Calendar


Calvin Lab Auditorium

Minkowski's mixed volume is a generalization of the ordinary n-volume to n-tuples of convex bodies. According to Bernstein's Theorem, the number of non-zero isolated complex solutions of a system of n polynomials in n variables is at most n! times the mixed volume of the convex hull of the support of each polynomial.

This invariant plays therefore an important role in polynomial solving, and a related object (a mixed subdivision) can be used as a starting system for homotopy algorithms.

I will present a new algorithm for mixed volume and mixed subdivision computation. The basic idea behind this algorithm is to explore a finite number of toric varieties. Its complexity can be bounded in terms of certain mixed volumes. In case all of the polytopes are n-dimensional, this algorithm is output sensitive.