The BKK root count in $\mathbf {C}^n$
HTML articles powered by AMS MathViewer
- by T. Y. Li and Xiaoshen Wang PDF
- Math. Comp. 65 (1996), 1477-1484 Request permission
Abstract:
The root count developed by Bernshtein, Kushnirenko and Khovanskii only counts the number of isolated zeros of a polynomial system in the algebraic torus $(\mathbf {C}^*)^n$. In this paper, we modify this bound slightly so that it counts the number of isolated zeros in $\mathbf {C}^n$. Our bound is, apparently, significantly sharper than the recent root counts found by Rojas and in many cases easier to compute. As a consequence of our result, the Huber-Sturmfels homotopy for finding all the isolated zeros of a polynomial system in $(\mathbf {C}^*)^n$ can be slightly modified to obtain all the isolated zeros in $\mathbf {C}^n$.References
- D. N. Bernstein, The number of roots of a system of equations, Funkcional. Anal. i Priložen. 9 (1975), no. 3, 1–4 (Russian). MR 0435072
- Felix E. Browder, Nonlinear mappings of analytic type in Banach spaces, Math. Ann. 185 (1970), 259–278. MR 259683, DOI 10.1007/BF01349949
- T. Bonnesen and W. Fenchel, Theory of convex bodies, BCS Associates, Moscow, ID, 1987. Translated from the German and edited by L. Boron, C. Christenson and B. Smith. MR 920366
- Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 0463157
- Birkett Huber and Bernd Sturmfels, A polyhedral method for solving sparse polynomial systems, Math. Comp. 64 (1995), no. 212, 1541–1555. MR 1297471, DOI 10.1090/S0025-5718-1995-1297471-4
- A. G. Hovanskiĭ, Newton polyhedra, and the genus of complete intersections, Funktsional. Anal. i Prilozhen. 12 (1978), no. 1, 51–61 (Russian). MR 487230
- A. G. Kušnirenko, Newton polyhedra and Bezout’s theorem, Funkcional. Anal. i Priložen. 10 (1976), no. 3, 82–83. (Russian). MR 0422272
- T.-Y. Li, Tim Sauer, and James A. Yorke, The random product homotopy and deficient polynomial systems, Numer. Math. 51 (1987), no. 5, 481–500. MR 910860, DOI 10.1007/BF01400351
- J. Maurice Rojas, A convex geometric approach to counting the roots of a polynomial system, Theoret. Comput. Sci. 133 (1994), no. 1, 105–140. Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993). MR 1294429, DOI 10.1016/0304-3975(93)00062-A
- J. M. Rojas and X. Wang, Counting affine roots via pointed Newton polytopes, to appear: J. of Complexity.
- I. R. Shafarevich, Basic algebraic geometry, Springer Study Edition, Springer-Verlag, Berlin-New York, 1977. Translated from the Russian by K. A. Hirsch; Revised printing of Grundlehren der mathematischen Wissenschaften, Vol. 213, 1974. MR 0447223
- Jan Verschelde and Ronald Cools, Symbolic homotopy construction, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 3, 169–183. MR 1226323, DOI 10.1007/BF01202036
- Jan Verschelde, Pierre Verlinden, and Ronald Cools, Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM J. Numer. Anal. 31 (1994), no. 3, 915–930. MR 1275120, DOI 10.1137/0731049
Additional Information
- T. Y. Li
- Affiliation: Department of Mathematics, Michigan State University, East Lansing, Michigan 48824-1027
- Email: li@mth.msu.edu
- Xiaoshen Wang
- Affiliation: Department of Mathematics and Computer Science, University of Central Arkansas, Conway, Arkansas 72035-0001
- Email: wangx@cc1.uca.edu
- Received by editor(s): November 23, 1994
- Received by editor(s) in revised form: October 9, 1995
- Additional Notes: The first author’s research was supported in part by NSF under Grant DMS-9504953 and by a Guggenheim Fellowship.
- © Copyright 1996 American Mathematical Society
- Journal: Math. Comp. 65 (1996), 1477-1484
- MSC (1991): Primary 52B20; Secondary 65H10, 68Q40
- DOI: https://doi.org/10.1090/S0025-5718-96-00778-8
- MathSciNet review: 1370853