Macaulay style formulas for sparse resultants

D’Andrea, Carlos

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

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.