The BKK root count in
Authors:
T. Y. Li and Xiaoshen Wang
Journal:
Math. Comp. 65 (1996), 14771484
MSC (1991):
Primary 52B20; Secondary 65H10, 68Q40
MathSciNet review:
1370853
Fulltext 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 HuberSturmfels 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
(55 #8034)
 2.
Felix
E. Browder, Nonlinear mappings of analytic type in Banach
spaces, Math. Ann. 185 (1970), 259–278. MR 0259683
(41 #4318)
 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 (88j:52001)
 4.
Robin
Hartshorne, Algebraic geometry, SpringerVerlag, New York,
1977. Graduate Texts in Mathematics, No. 52. MR 0463157
(57 #3116)
 5.
Birkett
Huber and Bernd
Sturmfels, A polyhedral method for solving sparse
polynomial systems, Math. Comp.
64 (1995), no. 212, 1541–1555. MR 1297471
(95m:65100), http://dx.doi.org/10.1090/S00255718199512974714
 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
(80b:14022)
 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
(54 #10263)
 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 (88j:65108), http://dx.doi.org/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
(95k:68090), http://dx.doi.org/10.1016/03043975(93)00062A
 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, SpringerVerlag, Berlin, 1977. Translated from the Russian by K.
A. Hirsch; Revised printing of Grundlehren der mathematischen
Wissenschaften, Vol. 213, 1974. MR 0447223
(56 #5538)
 12.
Jan
Verschelde and Ronald
Cools, Symbolic homotopy construction, Appl. Algebra Engrg.
Comm. Comput. 4 (1993), no. 3, 169–183. MR 1226323
(94c:68102), http://dx.doi.org/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
(94m:65084), http://dx.doi.org/10.1137/0731049
 1.
 D. N. Bernshtein, The number of roots of a system of equations, Functional Anal. Appl., 9(3): 183185, 1975. MR 55:8034
 2.
 F. E. Browder, Nonlinear mappings of analytic type in Banach spaces, Math. Ann., 185:259278, 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, SpringerVerlag, 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: 15411555, 1995. MR 95m:65100
 6.
 A. G. Khovanskii, Newton polyhedra and the genus of complete intersections, Functional Anal. Appl., 12(1):3846, 1978. MR 80b:14022
 7.
 A. G. Kushnirenko, Newton polytopes and the Bézout theorem, Functional Anal. Appl., 10(3):233235, 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:481500, 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), 105140. 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):169183, 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):915930, 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 488241027
Email:
li@mth.msu.edu
Xiaoshen Wang
Affiliation:
Department of Mathematics and Computer Science, University of Central Arkansas, Conway, Arkansas 720350001
Email:
wangx@cc1.uca.edu
DOI:
http://dx.doi.org/10.1090/S0025571896007788
PII:
S 00255718(96)007788
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 DMS9504953 and by a Guggenheim Fellowship.
Article copyright:
© Copyright 1996 American Mathematical Society
