Finding Mixed Cells in the Mixed Volume Computation

In practice, finding mixed cells in certain polyhedral subdivisions plays a dominating role when a polyhedral homotopy is employed to approximate all isolated zeros of polynomial systems. This paper gives a new algorithm for the mixed cell computation via a new formulation of the underlying linear programming problems. Numerical results show that the algorithm provides a major advance in the speed of computation with much less memory requirements. March 17, 2000. Final version received: November 2, 2000. Online publication: February 20, 2001.