Unmixing the mixed volume computation

Preprint English OPEN
Chen, Tianran;
  • Subject: 52B55, 65H10, 65H20 | Mathematics - Algebraic Geometry
    arxiv: Mathematics::Metric Geometry

Computing mixed volume of convex polytopes is an important problem in computational algebraic geometry. This paper establishes sufficient conditions under which the mixed volume of several convex polytopes exactly equals the normalized volume of the convex hull of their... View more
  • References (11)
    11 references, page 1 of 2

     X [1] Acebrn, J.A., Bonilla, L.L., Prez Vicente, C.J., Ritort, F., Spigler, R.: The Kuramoto model: A simple paradigm for synchronization phenomena. Reviews of Modern Physics 77(1), 137-185 (2005). DOI 10.1103/RevModPhys.77.137. URL http://link.aps.org/doi/10.1103/RevModPhys.77.137 [2] Allgower, E.L., Georg, K.: Numerical Continuation Methods: An Introduction. SpringerVerlag (1990) [3] Attardi, G., Traverso, C.: The PoSSo library for polynomial system solving. Proc. of AIHENP95 (1995) [4] Avis, D., Fukuda, K.: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete & Computational Geometry 8(3), 295-313 (1992).

    DOI 10.1007/BF02293050. URL http://link.springer.com/article/10.1007/BF02293050.

    Bibtex: avis pivoting 1992 [5] Avis, D., Fukuda, K.: Reverse Search for Enumeration. Discrete Applied Mathematics 65, 21-46 (1993) [6] Baillieul, J.: The critical point analysis of electric power systems. pp. 154-159. IEEE (1984). DOI 10.1109/CDC.1984.272291. URL http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=4047852 [7] Baillieul, J., Byrnes, C.: Geometric critical point analysis of lossless power system models.

    IEEE Transactions on Circuits and Systems 29(11), 724-737 (1982). DOI 10.1109/TCS.1982.

    1085093 [8] Beler, B., Enge, A., Fukuda, K.: Exact Volume Computation for Polytopes: A Practical Study. In: G. Kalai, G.M. Ziegler (eds.) Polytopes Combinatorics and Computation, no. 29 in DMV Seminar, pp. 131-154. Birkhuser Basel (2000). URL http://link.springer.com/chapter/10.1007/978-3-0348-8438-9_6 [9] Bernshtein, D.N.: The number of roots of a system of equations. Functional Analysis and its Applications 9(3), 183-185 (1975) [10] Bernshtein, D.N., Kushnirenko, A.G., Khovanskii, A.G.: Newton polyhedra. Uspekhi Mat. Nauk 31(3 (189)), 201-202 (1976). URL http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=3731&option_lang=eng [11] Canny, J., Rojas, J.M.: An optimal condition for determining the exact number of roots of a polynomial system. In: Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC '91, pp. 96-102. ACM, New York, NY, USA (1991).

    DOI 10.1145/120694.120707. URL http://doi.acm.org/10.1145/120694.120707 [12] Cartwright, D., Sturmfels, B.: The number of eigenvalues of a tensor. Linear Algebra and its Applications 438(2), 942-952 (2013). DOI 10.1016/j.laa.2011.05.040. URL http://www.sciencedirect.com/science/article/pii/S0024379511004629 [13] Chang, K.C., Pearson, K., Zhang, T.: On eigenvalue problems of real symmetric tensors. Journal of Mathematical Analysis and Applications 350(1), 416-422 (2009). DOI 10.1016/j.jmaa.2008.09.067. URL http://www.sciencedirect.com/science/article/pii/S0022247X08009724 [14] Chen, L., Han, L., Zhou, L.: Computing tensor eigenvalues via homotopy methods. arXiv:1501.04201 [math] (2015). URL http://arxiv.org/abs/1501.04201. ArXiv: 1501.04201 [15] Chen, T.: libtropicana: v0.1.1 (2016). URL https://doi.org/10.5281/zenodo.57133 [16] Chen, T., Lee, T.L., Li, T.Y.: Hom4ps-3: A Parallel Numerical Solver for Systems of Polynomial Equations Based on Polyhedral Homotopy Continuation Methods.

    SIAM Journal on Computing 27(2), 356-400 (1998). DOI 10.1137/S0097539794278384. URL http://epubs.siam.org/doi/abs/10.1137/S0097539794278384 [27] Emiris, I.Z., Canny, J.F.: Efficient incremental algorithms for the sparse resultant and the mixed volume. Journal of Symbolic Computation 20(2), 117-149 (1995). DOI 10.1006/jsco.

    1995.1041. URL http://www.sciencedirect.com/science/article/pii/S0747717185710413 [28] Gao, T., Li, T.Y.: Mixed volume computation via linear programming. Taiwanese Journal of Mathematics 4(4), pp. 599-619 (2000). DOI 10.11650/tjm.4.2000.1295. URL http://journal.taiwanmathsoc.org.tw/index.php/TJM/article/view/1295 [29] Gao, T., Li, T.Y.: Mixed volume computation for semi-mixed systems. Discrete & Computational Geometry 29(2), 257-277 (2003). DOI 10.1007/s00454-002-2837-x. URL http://link.springer.com/article/10.1007/s00454-002-2837-x [30] Gao, T., Li, T.Y., Wu, M.: Algorithm 846: MixedVol: a software package for mixed-volume computation. ACM Transactions on Mathematical Software (TOMS) 31(4), 555-560 (2005).

    DOI 10.1145/1114268.1114274. URL http://doi.acm.org/10.1145/1114268.1114274 [31] Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V.: Discriminants, Resultants, and Multidimensional Determinants. Mathematics: Theory & Applications. Birkhuser Boston (1994).

    Araki (ed.) International Symposium on Mathematical Problems in Theoretical Physics, no. 39 in Lecture Notes in Physics, pp. 420-422. Springer Berlin Heidelberg (1975). URL http://link.springer.com/chapter/10.1007/BFb0013365. DOI: 10.1007/BFb0013365 [45] Kushnirenko, A.G.: Newton polytopes and the Bezout theorem. Functional Analysis and Its Applications 10(3), 233-235 (1976). DOI 10.1007/BF01075534. URL http://link.springer.com/article/10.1007/BF01075534 [46] Lee, T.L., Li, T.Y.: Mixed volume computation in solving polynomial systems. Contemp.

  • Related Research Results (2)
  • Metrics
Share - Bookmark