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

MathSciNet review:
1370853

Full-text PDF Free Access

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. Bernstein,*The number of roots of a system of equations*, Funkcional. Anal. i Priložen.**9**(1975), no. 3, 1–4 (Russian). MR**0435072****2.**Felix E. Browder,*Nonlinear mappings of analytic type in Banach spaces*, Math. Ann.**185**(1970), 259–278. MR**0259683****3.**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****4.**Robin Hartshorne,*Algebraic geometry*, Springer-Verlag, New York-Heidelberg, 1977. Graduate Texts in Mathematics, No. 52. MR**0463157****5.**Birkett Huber and Bernd Sturmfels,*A polyhedral method for solving sparse polynomial systems*, Math. Comp.**64**(1995), no. 212, 1541–1555. MR**1297471**, 10.1090/S0025-5718-1995-1297471-4**6.**A. G. Hovanskiĭ,*Newton polyhedra, and the genus of complete intersections*, Funktsional. Anal. i Prilozhen.**12**(1978), no. 1, 51–61 (Russian). MR**487230****7.**A. G. Kušnirenko,*Newton polyhedra and Bezout’s theorem*, Funkcional. Anal. i Priložen.**10**(1976), no. 3, 82–83. (Russian). MR**0422272****8.**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**, 10.1007/BF01400351**9.**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**, 10.1016/0304-3975(93)00062-A**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 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****12.**Jan Verschelde and Ronald Cools,*Symbolic homotopy construction*, Appl. Algebra Engrg. Comm. Comput.**4**(1993), no. 3, 169–183. MR**1226323**, 10.1007/BF01202036**13.**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**, 10.1137/0731049

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:
http://dx.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