The BKK root count in

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 . In this paper, we modify this bound slightly so that it counts the number of isolated zeros in . 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 can be slightly modified to obtain all the isolated zeros in .

**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**

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