Tangan Gao
Abstract
MixedVol is a C++ software package that computes the mixed volume of n finite subsets of ℤn or the support of a system of n polynomials in n variables. The software produces the mixed volume as well as the mixed cells. The mixed cells are crucial for solving polynomial systems by the polyhedral homotopy continuation method. The software leads existing codes for mixed-volume computation in speed by a substantial margin and its memory requirement is very low.
Supplemental Material
Available for Download
Software for "MixedVol: a software package for mixed-volume computation"
- Emiris, I. Z. and Canny, J. F. 1995. Efficient incremental algorithms for the sparse resultant and the mixed volume. J. Symb. Comput. 20, 117--149. Software package available online at http://www--sop.inria.fr/galaad/logiciels/emiris/soft_geo.html. Google Scholar
- Gao, T. and Li, T. Y. 2003. Mixed volume computation for semimixed systems. Discrete Comput. Geom. 29, 257--277.Google Scholar
- Huber, B. and Sturmfels, B. 1995. A polyhedral method for solving sparse polynomial systems. Math. Comp. 64, 1541--1555. Google Scholar
- Li, T. Y. and Li, X. 2001. Finding mixed cells in the mixed volume computation. Found. Comput. Math. 1, 161--181. Software package available online at http://www.math.msu.edu/~li.Google Scholar
- Takeda, A., Kojima, M., and Fujisawa, K. 2002. Enumeration of all solutions of a combinatorial linear inequality system arising from the polyhedral homotopy continuation method. J. Oper. Res. Soc. Japan 45, 64--82. Software package available online at http://www.is.titech.ac.jp/~kojima.Google Scholar
- Verschelde, J. 1999. Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation. ACM Trans. Math. Softw. 25, 251--276. Software package available online at http://www2.math.uic.edu/~jan. Google Scholar
- Verschelde, J., Gatermann, K., and Cools, R. 1996. Mixed-volume computation by dynamic lifting applied to polynomial system solving. Discrete Comput. Geom. 16, 69--112.Google Scholar
Index Terms
- Algorithm 846: MixedVol: a software package for mixed-volume computation
Recommendations
A subdivision-based algorithm for the sparse resultant
Multivariate resultants generalize the Sylvester resultant of two polynomials and characterize the solvability of a polynomial system. They also reduce the computation of all common roots to a problem in linear algebra. We propose a determinantal ...
The DMM bound: multivariate (aggregate) separation bounds
ISSAC '10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic ComputationIn this paper we derive aggregate separation bounds, named after Davenport-Mahler-Mignotte (DMM), on the isolated roots of polynomial systems, specifically on the minimum distance between any two such roots. The bounds exploit the structure of the ...
Exact resultants for corner-cut unmixed multivariate polynomial systems using the Dixon formulation
Special issue: International symposium on symbolic and algebraic computation (ISSAC 2002)Structural conditions on the support of a multivariate polynomial system are developed for which the Dixon-based resultant methods compute exact resultants. The concepts of a corner-cut support and almost corner-cut support of an unmixed polynomial ...
Comments