×

zbMATH — the first resource for mathematics

Computing mixed volume and all mixed cells in quermassintegral time. (English) Zbl 1383.65050
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. In this paper, the author introduces a geometric algorithm. Its complexity is bounded in the average and probability-one settings in terms of some geometric invariants: quermassintegrals associated with 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 are available. For some of those families, an asymptotic running time gain over the best code available at this time was noticed.

MSC:
65H10 Numerical computation of solutions to systems of equations
52A39 Mixed volumes and related topics in convex geometry
14M25 Toric varieties, Newton polyhedra, Okounkov bodies
14N10 Enumerative problems (combinatorial problems) in algebraic geometry
52B55 Computational aspects related to convexity
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barvinok, A, Computing mixed discriminants, mixed volumes, and permanents, Discrete Comput. Geom., 18, 205-237, (1997) · Zbl 0876.68113
[2] Bernstein, DN, The number of roots of a system of equations, Funkcional. Anal. i Priložen., 9, 1-4, (1975)
[3] Bernstein, DN; Kušnirenko, AG; Hovanskĭ, AG, Newton polyhedra, Uspehi Mat. Nauk 31, 3, 201-202, (1976)
[4] Chen, Tianran; Lee, Tsung-Lin; Li, Tien-Yien, Mixed volume computation in parallel, Taiwanese J. Math., 18, 93-114, (2014) · Zbl 1357.52009
[5] Cartwright, Dustin; Payne, Sam, Connectivity of tropicalizations, Math. Res. Lett., 19, 1089-1095, (2012) · Zbl 1291.14091
[6] Demmel, James W. 1997. Applied numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA. · Zbl 0879.65017
[7] Dyer, Martin; Gritzmann, Peter; Hufnagel, Alexander, On the complexity of computing mixed volumes, SIAM J. Comput., 27, 356-400, (1998) · Zbl 0909.68193
[8] Emiris, Ioannis Z, On the complexity of sparse elimination, J. Complexity, 12, 134-166, (1996) · Zbl 0935.12008
[9] Emiris, Ioannis Z; Canny, John F, Efficient incremental algorithms for the sparse resultant and the mixed volume, J. Symbolic Comput., 20, 117-149, (1995) · Zbl 0843.68036
[10] Emiris, Ioannis Z. and Vissarion Fisikopoulos. 2014. Efficient Random-Walk Methods for Ap- proximating Polytope Volume, 30th Annual Symposium on Computational Geometry, SOCG’14, Kyoto, Japan, June 08 - 11, 2014, pp. 318. · Zbl 1395.68300
[11] Emiris, Ioannis Z. and Raimundas Vidunas. 2014. Root counts of semi-mixed systems, and an application to counting Nash equilibria, ISSAC’14, pp. 154-161. · Zbl 1325.68275
[12] Gao, Tangan; Li, TY, Mixed volume computation via linear programming, Taiwanese J. Math., 4, 599-619, (2000) · Zbl 0997.65081
[13] Gao, Tangan; Li, TY; Mengnien, Wu, Algorithm 846: mixedvol: a software pack- age for mixed-volume computation, ACM Trans. Math. Software, 31, 555-560, (2005) · Zbl 1136.65320
[14] Gurvits, Leonid, A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor, Discrete Comput. Geom., 41, 533-555, (2009) · Zbl 1183.68661
[15] Huber, Birkett; Sturmfels, Bernd, A polyhedral method for solving sparse polynomial systems, Math. Comp., 64, 1541-1555, (1995) · Zbl 0849.65030
[16] Jensen, Anders. 2016. Tropical Homotopy Continuation, available at http://arxiv.org/abs/1601.02818. · Zbl 1350.14045
[17] Khachiyan, L. G. 1989. The problem of calculating the volume of a polyhedron is enumeratively hard, Uspekhi Mat. Nauk 44, no. 3(267), 179-180, doi:10.1070/RM1989v044n03ABEH002136 (Russian); English transl.,. 1989, Russian Math. Surveys 44, no. 3, 199-200. · Zbl 0676.68016
[18] Knuth, Donald E. 1998. The art of computer programming. Vol. 3, Addison-Wesley, Reading, MA. · Zbl 0895.65001
[19] Le Gall, François. 2014. Powers of Tensors and Fast Matrix Multiplication, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), pp. 296- 303. · Zbl 1325.65061
[20] Lee, Tsung-Lin and Tien-Yien Li. 2011. Mixed volume computation in solving polynomial system- s, Randomization, relaxation, and complexity in polynomial equation solving, Contemp. Math., vol. 556, Amer. Math. Soc., Providence, RI, pp. 97-112, doi:10.1090/conm/556/11009, (to appear in print). · Zbl 1416.65145
[21] Li, TY; Li, Xing, Finding mixed cells in the mixed volume computation, Found. Comput. Math., 1, 161-181, (2001) · Zbl 1012.65019
[22] Maclagan, Diane and Bernd Sturmfels. 2015. Introduction to Tropical Geometry, American Mathematical Society, Providence, RI. · Zbl 1321.14048
[23] Malajovich, Gregorio, On the expected number of zeros of nonlinear equations, Found. Comput. Math., 13, 867-884, (2013) · Zbl 1285.32005
[24] Malajovich, Gregorio; Maurice Rojas, J, High probability analysis of the condition number of sparse polynomial systems, Theoret. Comput. Sci., 315, 524-555, (2004) · Zbl 1067.65053
[25] Minkowski, Hermann, Sur LES surfaces convexes fermées, C.R. Acad. Sci. Paris, 132, 21-24, (1901) · JFM 32.0386.02
[26] Mizutani, Tomohiko and Akiko Takeda. 2008. DEMiCs: a software package for computing the mixed volume via dynamic enumeration of all mixed cells, Software for algebraic geometry, IMA Vol. Math. Appl., vol. 148, Springer, New York, pp. 59-79, doi:10.1007/978-0-387-78133-4, (to appear in print). · Zbl 1148.68580
[27] Mizutani, Tomohiko; Takeda, Akiko; Kojima, Masakazu, Dynamic enumeration of all mixed cells, Discrete Comput. Geom., 37, 351-367, (2007) · Zbl 1113.65055
[28] Morgan, Alexander. 1987. Solving polynomial systems using continuation for engineering and scientific problems, Prentice Hall, Inc., Englewood Cliffs, NJ. · Zbl 0733.65031
[29] Preparata, Franco P. and Michael Ian Shamos. 1985. Computational geometry, Texts and Monographs in Computer Science, Springer-Verlag, New York. An introduction.
[30] Uhler, Caroline, Geometry of maximum likelihood estimation in Gaussian graphical models, Ann. Statist., 40, 238-261, (2012) · Zbl 1246.62140
[31] Vassilevska Williams, Virginia. 2012. Multiplying matrices faster than Coppersmith-Winograd, Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pp. 887-898. · Zbl 1286.65056
[32] Verschelde, Algorithm 795: phcpack: A general-purpose solver for polynomial systems by homotopy continuation, ACM Transactions on Mathematical Software, 25, 251-276, (1999) · Zbl 0961.65047
[33] Verschelde, J; Gatermann, K; Cools, R, Mixed-volume computation by dynamic lift- ing applied to polynomial system solving, Discrete Comput. Geom., 16, 69-112, (1996) · Zbl 0854.68111
[34] Yu, Josephine. 2015. Do most polynomials generate a prime ideal?, available at http://arxiv.org/abs/1509.02050. · Zbl 1370.13018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.