MIXED-VOLUME COMPUTATION BY DYNAMIC LIFTING APPLIED TO POLYNOMIAL SYSTEM SOLVING

The aim of this paper is to present a flexible approach for the effici ent computation of the mixed volume of a tuple of polytopes. In order to compute the mixed volume, a mixed subdivision of the tuple of polyt opes is needed, which can be obtained by embedding the polytopes in a higher-dimensional space, i.e., by lifting them. Dynamic lifting is op posed 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 po int really influences the mixed volume. Conservative lifting functions have been developed for this purpose. This provides us with a determi nistic 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 meth ods for the solution of polynomial systems are investigated and applic ations are presented.