Mixed-volume computation by dynamic lifting applied to polynomial system solving

The aim of this paper is to present a flexible approach for the efficient computation of the mixed volume of a tuple of polytopes. In order to compute the mixed volume, a mixed subdivision of the tuple of polytopes is needed, which can be obtained by embedding the polytopes in a higher-dimensional space, i.e., by lifting them. Dynamic lifting is opposed to the static approach. This means that one considers one point at a time and only fixes the value of the lifting function when the point really influences the mixed volume. Conservative lifting functions have been developed for this purpose. This provides us with a deterministic manipulation of the lifting for computing mixed volumes, which rules out randomness conditions. Cost estimates for the algorithm are given. The implications of dynamic lifting on polyhedral homotopy methods for the solution of polynomial systems are investigated and applications are presented.