|
The BKK root count in 
Author(s):
T.
Y.
Li;
Xiaoshen
Wang.
Journal:
Math. Comp.
65
(1996),
1477-1484.
MSC (1991):
Primary 52B20;
Secondary 65H10, 68Q40
Retrieve article in:
PDF
This article is available free of charge
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  .
References:
- 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
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:
10.1090/S0025-5718-96-00778-8
PII:
S 0025-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.
Copyright of article:
Copyright
1996,
American Mathematical Society
|
Comments: webmaster@ams.org