A polyhedral method for solving sparse polynomial systems

Huber, Birkett; Sturmfels, Bernd

doi:10.1090/S0025-5718-1995-1297471-4

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

An optimal condition for determining the exact number of roots of a polynomial system

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

On the complexity of computing mixed volumes

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