Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

The BKK root count in $\mathbf {C}^n$


Authors: T. Y. Li and Xiaoshen Wang
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
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. D. N. Bernshtein, The number of roots of a system of equations, Functional Anal. Appl., 9(3): 183-185, 1975. MR 55:8034
  • 2. F. E. Browder, Nonlinear mappings of analytic type in Banach spaces, Math. Ann., 185:259-278, 1970. MR 41:4318
  • 3. T. Bonnesen and W. Fenchel, Theory of convex bodies , BCS Associates, Moscow, Idaho, 1987. MR 88j:52001
  • 4. R. Hartshorne, Algebraic geometry, Graduate Texts in Math., 52, Springer-Verlag, Berlin, Heidelberg, New York, 1977. MR 57:3116
  • 5. B. Huber and B. Sturmfels, A polyhedral method for solving sparse polynomial systems, Math. Comp., 64: 1541-1555, 1995. MR 95m:65100
  • 6. A. G. Khovanskii, Newton polyhedra and the genus of complete intersections, Functional Anal. Appl., 12(1):38-46, 1978. MR 80b:14022
  • 7. A. G. Kushnirenko, Newton polytopes and the Bézout theorem, Functional Anal. Appl., 10(3):233-235, 1976. MR 54:10263
  • 8. T. Y. Li, T. Sauer and J.A. Yorke, The random product homotopy and deficient polynomial systems, Numer. Math., 51:481-500, 1987. MR 88j:65108
  • 9. J. M. Rojas, A convex geometric approach to counting the roots of a polynomial system, Theoret. Comput. Sci. 133 (1994), 105--140. MR 95k:68090
  • 10. J. M. Rojas and X. Wang, Counting affine roots via pointed Newton polytopes, to appear: J. of Complexity.
  • 11. I. R. Shafarevich, Basic algebraic geometry, Springer, New York, 1977. MR 56:5538
  • 12. J. Verschelde and R. Cools, Symbolic homotopy construction, Applicable Algebra in Engineering, Communication and Computing, 4(3):169-183, 1993. MR 94c:68102
  • 13. J. Verschelde, P. Verlinden and R. Cools, Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM J. Numer. Anal., 31(3):915-930, 1994. MR 94m:65084

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 52B20, 65H10, 68Q40

Retrieve articles in all journals with MSC (1991): 52B20, 65H10, 68Q40


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

DOI: https://doi.org/10.1090/S0025-5718-96-00778-8
Keywords: BKK bound, mixed volume, homotopy continuation
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.
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society