Macaulay style formulas for sparse resultants
Author:
Carlos D’Andrea
Journal:
Trans. Amer. Math. Soc. 354 (2002), 2595-2629
MSC (2000):
Primary 13P99, 68W30
DOI:
https://doi.org/10.1090/S0002-9947-02-02910-0
Published electronically:
February 1, 2002
MathSciNet review:
1895195
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
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.
- 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 https://doi.org/10.1016/S0747-7171%2808%2980012-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 https://doi.org/10.1007/3-540-56686-4_36
- 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.
- M. Chardin. The Resultant via a Koszul Complex. In F. Eyssette and A. Galligo, editors, Computational Algebraic Geometry, volume 109 of Progress in Mathematics, 29-39. Birkhäuser, Boston, 1993.
- 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
- 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 https://doi.org/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
- 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
- Birkett Huber and Bernd Sturmfels, A polyhedral method for solving sparse polynomial systems, Math. Comp. 64 (1995), no. 212, 1541–1555. MR 1297471, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0304-3975%2881%2990064-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 https://doi.org/10.1007/BF02572411
- J. Renegar. On the computational complexity and geometry of the first-order theory of the reals, parts I, II, III. J. Symbolic Computacion, 13(3): 255-352, 1992.
- 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 https://doi.org/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 https://doi.org/10.1023/A%3A1022497624378
- 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 https://doi.org/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 https://doi.org/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.
Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 13P99, 68W30
Retrieve articles in all journals with MSC (2000): 13P99, 68W30
Additional Information
Carlos D’Andrea
Affiliation:
Departamento de Matemática, F.C.E. y N., Universidad de Buenos Aires, Pabellón I, Ciudad Universitaria (1428), Buenos Aires, Argentina
MR Author ID:
652039
Email:
cdandrea@dm.uba.ar
Received by editor(s):
June 13, 2001
Received by editor(s) in revised form:
September 26, 2001
Published electronically:
February 1, 2002
Additional Notes:
Partially supported by Universidad de Buenos Aires, grant TX094, and Agencia Nacional de Promoción Científica y Tecnológica (Argentina), grant 3-6568.
Article copyright:
© Copyright 2002
American Mathematical Society