An Efficient Computation of Mixed Volume

Ioannis Emiris

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-93-734
April 1993

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/CSD-93-734.pdf

The Mixed Volume of n polytopes in n-dimensional space is a multilinear function with respect to Minkowski addition and scalar multiplication that generalizes the notion of volume. The current interest in efficient methods for computing it is mainly due to Bernstein's theorem which bounds the number of common roots of a system of polynomial equations by the Mixed Volume of the respective Newton polytopes. In this paper we propose an algorithm that uses polyhedral techniques to significantly improve upon the efficiency of the method based on evaluating the inclusion-exclusion formula and obtain a practical algorithm.

BibTeX citation:

@techreport{Emiris:CSD-93-734,
    Author = {Emiris, Ioannis},
    Title = {An Efficient Computation of Mixed Volume},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {Apr},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6027.html},
    Number = {UCB/CSD-93-734},
    Abstract = {The Mixed Volume of <i>n</i> polytopes in <i>n</i>-dimensional space is a multilinear function with respect to Minkowski addition and scalar multiplication that generalizes the notion of volume. The current interest in efficient methods for computing it is mainly due to Bernstein's theorem which bounds the number of common roots of a system of polynomial equations by the Mixed Volume of the respective Newton polytopes. In this paper we propose an algorithm that uses polyhedral techniques to significantly improve upon the efficiency of the method based on evaluating the inclusion-exclusion formula and obtain a practical algorithm.}
}

EndNote citation:

%0 Report
%A Emiris, Ioannis
%T An Efficient Computation of Mixed Volume
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/CSD-93-734
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6027.html
%F Emiris:CSD-93-734