Macaulay style formulas for sparse resultants

D’Andrea, Carlos

doi:10.1090/S0002-9947-02-02910-0

Macaulay style formulas for sparse resultants
HTML articles powered by AMS MathViewer

by Carlos D’Andrea PDF

Trans. Amer. Math. Soc. 354 (2002), 2595-2629 Request permission

Abstract:

We present formulas for computing the resultant of sparse polynomials as a quotient of two determinants, the denominator being a minor of the numerator. These formulas extend the original formulation given by Macaulay for homogeneous polynomials.

References

W. Auzinger and H. J. Stetter, An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations, Numerical mathematics, Singapore 1988, Internat. Schriftenreihe Numer. Math., vol. 86, Birkhäuser, Basel, 1988, pp. 11–30. MR 1022943
E. Bézout. Théorie Générale des Équations Algébriques. Paris, 1779.
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
John Canny, The complexity of robot motion planning, ACM Doctoral Dissertation Awards, vol. 1987, MIT Press, Cambridge, MA, 1988. MR 952555
John Canny, Generalised characteristic polynomials, J. Symbolic Comput. 9 (1990), no. 3, 241–250. MR 1056626, DOI 10.1016/S0747-7171(08)80012-0
John Canny and Ioannis Emiris, An efficient algorithm for the sparse mixed resultant, Applied algebra, algebraic algorithms and error-correcting codes (San Juan, PR, 1993) Lecture Notes in Comput. Sci., vol. 673, Springer, Berlin, 1993, pp. 89–104. MR 1251972, DOI 10.1007/3-540-56686-4_{3}6
J. F. Canny and I. Z. Emiris. A Subdivision-based Algorithm for the Sparse Resultant. J. ACM, 47(3):417–451, May 2000.
Eduardo Cattani, Alicia Dickenstein, and Bernd Sturmfels, Residues and resultants, J. Math. Sci. Univ. Tokyo 5 (1998), no. 1, 119–148. MR 1617074
A. Cayley. On the theory of elimination. Cambridge and Dublin Math. J. 3 (1848), 116-120.
Hidegorô Nakano, Über Abelsche Ringe von Projektionsoperatoren, Proc. Phys.-Math. Soc. Japan (3) 21 (1939), 357–375 (German). MR 94
David A. Cox, The homogeneous coordinate ring of a toric variety, J. Algebraic Geom. 4 (1995), no. 1, 17–50. MR 1299003
David Cox, John Little, and Donal O’Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer-Verlag, New York, 1998. MR 1639811, DOI 10.1007/978-1-4757-6911-1
C. D’Andrea and A. Dickenstein. Explicit Formulas for the Multivariate Resultant. Journal of Pure and Applied Algebra, Vol. 164, No. 1-2, 59-86, 2001.
M. Demazure. Une définition constructive du résultant. Notes Informelles de Calcul Formel 2, prepublication du Centre de Mathématiques de l’ École Polytechnique, 1984.
A. L. Dixon. The Eliminant of three quantics in two independent variables. Proc. London Math. Soc. 6 (1908), 49–69.
I. Z. Emiris. Sparse Elimination and Applications in Kinematics. Ph.D. Thesis, University of California at Berkeley, 1994.
I. Z. Emiris. A Complete Implementation for Computing General Dimensional Convex Hulls. Intern. J. Computational Geometry & Applications, Special Issue on Geometric Software, n.2, vol. 223-253, 1998.
Ioannis Z. Emiris and Bernard Mourrain, Matrices in elimination theory, J. Symbolic Comput. 28 (1999), no. 1-2, 3–44. Polynomial elimination—algorithms and applications. MR 1709416, DOI 10.1006/jsco.1998.0266
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, A. V. Zelevinskiĭ, and M. M. Kapranov, Discriminants of polynomials in several variables and triangulations of Newton polyhedra, Algebra i Analiz 2 (1990), no. 3, 1–62 (Russian); English transl., Leningrad Math. J. 2 (1991), no. 3, 449–505. MR 1073208
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
Birkett Huber and Bernd Sturmfels, A polyhedral method for solving sparse polynomial systems, Math. Comp. 64 (1995), no. 212, 1541–1555. MR 1297471, DOI 10.1090/S0025-5718-1995-1297471-4
J. P. Jouanolou, Formes d’inertie et résultant: un formulaire, Adv. Math. 126 (1997), no. 2, 119–250 (French). MR 1442307, DOI 10.1006/aima.1996.1609
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
T.Krick, L.M. Pardo, and M. Sombra. Sharp estimates for the arithmetic Nullstellensatz. Duke Mathematical Journal, Vol. 109, No. 3, 521-598, 2001.
Daniel Lazard, Résolution des systèmes d’équations algébriques, Theoret. Comput. Sci. 15 (1981), no. 1, 77–110 (French, with English summary). MR 619687, DOI 10.1016/0304-3975(81)90064-5
F. Macaulay. Some Formulae in Elimination. Proc. London Math. Soc. 1 33, 3–27, 1902.
M. Minimair Sparse Resultant under Vanishing Coefficients. Preprint, 2001. Available at http://minimair.org
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
Erich Rothe, Topological proofs of uniqueness theorems in the theory of differential and integral equations, Bull. Amer. Math. Soc. 45 (1939), 606–613. MR 93, DOI 10.1090/S0002-9904-1939-07048-1
J. Maurice Rojas, Solving degenerate sparse polynomial systems faster, J. Symbolic Comput. 28 (1999), no. 1-2, 155–186. Polynomial elimination—algorithms and applications. MR 1709421, DOI 10.1006/jsco.1998.0271
Bernd Sturmfels, Sparse elimination theory, Computational algebraic geometry and commutative algebra (Cortona, 1991) Sympos. Math., XXXIV, Cambridge Univ. Press, Cambridge, 1993, pp. 264–298. MR 1253995
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
Bernd Sturmfels, Introduction to resultants, Applications of computational algebraic geometry (San Diego, CA, 1997) Proc. Sympos. Appl. Math., vol. 53, Amer. Math. Soc., Providence, RI, 1998, pp. 25–39. MR 1602347, DOI 10.1090/psapm/053/1602347
Bernd Sturmfels and Andrei Zelevinsky, Multigraded resultants of Sylvester type, J. Algebra 163 (1994), no. 1, 115–127. MR 1257308, DOI 10.1006/jabr.1994.1007
J. J. Sylvester. On a Theory of Syzygetic Relations of Two Rational Integral Functions, Comprising an Application to the Theory of Sturm’s Functions, and that of the Greatest Algebraic Common Measure. Philosophical Trans., 143 (1853), 407-548.
Jerzy Weyman and Andrei Zelevinsky, Determinantal formulas for multigraded resultants, J. Algebraic Geom. 3 (1994), no. 4, 569–597. MR 1297847
M. Zhang, E. W. Chionh, and R. N. Goldman. Rectangular corner cutting Sylvester $\mathcal {A}$-resultant. In Proc. ACM Intern. Symp. on Symbolic and Algebraic Computation, 2000.