Computing mixed volume and all mixed cells in quermassintegral time
For researchers solving sparse polynomial systems, this provides a theoretically grounded algorithm with non-exponential average-case complexity, though practical gains are incremental.
The paper introduces a geometric algorithm for computing mixed volume and all mixed cells of sparse polynomial systems, with complexity bounded by quermassintegrals. Numerical results show output-sensitive running time and asymptotic gains over existing code.
The mixed volume counts the roots of generic sparse polynomial systems. Mixed cells are used to provide starting systems for homotopy algorithms that can find all those roots, and track no unnecessary path. Up to now, algorithms for that task were of enumerative type, with no general non- exponential complexity bound. A geometric algorithm is introduced in this paper. Its complexity is bounded in the average and probability-one settings in terms of some geometric invariants: quermassintegrals associated to the tuple of convex hulls of the support of each polynomial. Besides the complexity bounds, numerical results are reported. Those are consistent with an output- sensitive running time for each benchmark family where data is available. For some of those families, an asymptotic running time gain over the best code available at this time was noticed.