The BKK root count in \(\mathbb{C}^ n\). (English) Zbl 0855.65053
Summary: The root count developed by Bernshtein, Kushnirenko and Khovanskij (BKK root count) only counts the number of isolated zeros of a polynomial system in the algebraic torus \((\mathbb{C}^*)^n\). In this paper, we modify this bound slightly so that it counts the number of isolated zeros in \(\mathbb{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 \((\mathbb{C}^*)^n\) can be slightly modified to obtain all the isolated zeros in \(\mathbb{C}^n\).
MSC:
| 65H10 | Numerical computation of solutions to systems of equations |
| 68W30 | Symbolic computation and algebraic computation |
References:
| [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). |
| [2] | Felix E. Browder, Nonlinear mappings of analytic type in Banach spaces, Math. Ann. 185 (1970), 259 – 278. · Zbl 0224.47033 · doi:10.1007/BF01349949 |
| [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. · Zbl 0628.52001 |
| [4] | Robin Hartshorne, Algebraic geometry, Springer-Verlag, New York-Heidelberg, 1977. Graduate Texts in Mathematics, No. 52. · Zbl 0367.14001 |
| [5] | Birkett Huber and Bernd Sturmfels, A polyhedral method for solving sparse polynomial systems, Math. Comp. 64 (1995), no. 212, 1541 – 1555. · Zbl 0849.65030 |
| [6] | A. G. Hovanskiĭ, Newton polyhedra, and the genus of complete intersections, Funktsional. Anal. i Prilozhen. 12 (1978), no. 1, 51 – 61 (Russian). |
| [7] | A. G. Kušnirenko, Newton polyhedra and Bezout’s theorem, Funkcional. Anal. i Priložen. 10 (1976), no. 3, 82 – 83. (Russian). |
| [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. · Zbl 0656.65055 · doi: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). · Zbl 0812.65040 · doi: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. · Zbl 0885.12007 |
| [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. · Zbl 0284.14001 |
| [12] | Jan Verschelde and Ronald Cools, Symbolic homotopy construction, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 3, 169 – 183. · Zbl 0804.65058 · doi: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. · Zbl 0809.65048 · doi:10.1137/0731049 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
