A polyhedral method for solving sparse polynomial systems
HTML articles powered by AMS MathViewer
- by Birkett Huber and Bernd Sturmfels PDF
- Math. Comp. 64 (1995), 1541-1555 Request permission
Abstract:
A continuation method is presented for computing all isolated roots of a semimixed sparse system of polynomial equations. We introduce mixed subdivisions of Newton polytopes, and we apply them to give a new proof and algorithm for Bernstein’s theorem on the expected number of roots. This results in a numerical homotopy with the optimal number of paths to be followed. In this homotopy there is one starting system for each cell of the mixed subdivision, and the roots of these starting systems are obtained by an easy combinatorial construction.References
- Eugene L. Allgower and Kurt Georg, Numerical continuation methods, Springer Series in Computational Mathematics, vol. 13, Springer-Verlag, Berlin, 1990. An introduction. MR 1059455, DOI 10.1007/978-3-642-61257-2
- 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
- U. Betke, Mixed volumes of polytopes, Arch. Math. (Basel) 58 (1992), no. 4, 388–391. MR 1152628, DOI 10.1007/BF01189930
- Louis J. Billera and Bernd Sturmfels, Fiber polytopes, Ann. of Math. (2) 135 (1992), no. 3, 527–549. MR 1166643, DOI 10.2307/2946575 J. Canny and J. M. Rojas, An optimal condition for determining the exact number of roots of a polynomial system, Proceedings of ISSAC 91 (Bonn, Germany), ACM Press, New York, 1991, pp. 96-102.
- F. J. Drexler, A homotopy method for the calculation of all zeros of zero-dimensional polynomial ideals, Developments in statistics, Vol. 1, Academic Press, New York, 1978, pp. 69–93. MR 505422 M. Dyer, P. Gritzmann, and A. Hufnagel, On the complexity of computing mixed volumes, Manuscript, Trier, Germany, 1994.
- William Fulton, Introduction to toric varieties, Annals of Mathematics Studies, vol. 131, Princeton University Press, Princeton, NJ, 1993. The William H. Roever Lectures in Geometry. MR 1234037, DOI 10.1515/9781400882526
- I. M. Gel′fand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1264417, DOI 10.1007/978-0-8176-4771-1
- M. M. Kapranov, B. Sturmfels, and A. V. Zelevinsky, Chow polytopes and general resultants, Duke Math. J. 67 (1992), no. 1, 189–218. MR 1174606, DOI 10.1215/S0012-7094-92-06707-X
- Carl W. Lee, Regular triangulations of convex polytopes, Applied geometry and discrete mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 4, Amer. Math. Soc., Providence, RI, 1991, pp. 443–456. MR 1116369
- Peter McMullen and Rolf Schneider, Valuations on convex bodies, Convexity and its applications, Birkhäuser, Basel, 1983, pp. 170–247. MR 731112
- Alexander Morgan and Andrew Sommese, A homotopy for solving general polynomial systems that respects $m$-homogeneous structures, Appl. Math. Comput. 24 (1987), no. 2, 101–113. MR 914806, DOI 10.1016/0096-3003(87)90063-4
- Paul Pedersen and Bernd Sturmfels, Product formulas for resultants and Chow forms, Math. Z. 214 (1993), no. 3, 377–396. MR 1245200, DOI 10.1007/BF02572411
- 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
- Bernd Sturmfels, On the Newton polytope of the resultant, J. Algebraic Combin. 3 (1994), no. 2, 207–236. MR 1268576, DOI 10.1023/A:1022497624378
- 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, DOI 10.1137/0731049
- Robert J. Walker, Algebraic curves, Springer-Verlag, New York-Heidelberg, 1978. Reprint of the 1950 edition. MR 513824
Additional Information
- © Copyright 1995 American Mathematical Society
- Journal: Math. Comp. 64 (1995), 1541-1555
- MSC: Primary 65H20; Secondary 65H10
- DOI: https://doi.org/10.1090/S0025-5718-1995-1297471-4
- MathSciNet review: 1297471