×

Macaulay style formulas for sparse resultants. (English) Zbl 0987.13019

From the paper: Let \({\mathcal A}_0, \dots, {\mathcal A}_n\) be finite subsets of \(\mathbb{Z}^n\) and consider \(n+1\) polynomials \(f_0,\dots,f_n\) in \(n\) variables such that \(\text{supp} (f_i)={\mathcal A}_i\), \(i=0,\dots,n\). The sparse resultant is an irreducible polynomial in the coefficients of \(f_0,\dots,f_n\), which vanishes if the system \(f_i=0\), \(i=0,\dots,n\) has a solution in an algebraically closed field. It will be denoted by \(\text{Res}_{\mathcal A}(f_0, \dots,f_n)\), where \({\mathcal A}:= ({\mathcal A}_0,\dots, {\mathcal A}_n)\).
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 F. S. Macaulay for homogeneous polynomials.

MSC:

13P05 Polynomials, factorization in commutative rings
13-04 Software, source code, etc. for problems pertaining to commutative algebra
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 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. · Zbl 0658.65047
[2] E. Bézout. Théorie Générale des Équations Algébriques. Paris, 1779.
[3] D. N. Bernstein, The number of roots of a system of equations, Funkcional. Anal. i Priložen. 9 (1975), no. 3, 1 – 4 (Russian).
[4] John Canny, The complexity of robot motion planning, ACM Doctoral Dissertation Awards, vol. 1987, MIT Press, Cambridge, MA, 1988. · Zbl 0668.14016
[5] John Canny, Generalised characteristic polynomials, J. Symbolic Comput. 9 (1990), no. 3, 241 – 250. · Zbl 0704.12004 · doi:10.1016/S0747-7171(08)80012-0
[6] 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. · Zbl 0789.65034 · doi:10.1007/3-540-56686-4_36
[7] J. F. Canny and I. Z. Emiris. A Subdivision-based Algorithm for the Sparse Resultant. J. ACM, 47(3):417-451, May 2000. CMP 2000:15
[8] Eduardo Cattani, Alicia Dickenstein, and Bernd Sturmfels, Residues and resultants, J. Math. Sci. Univ. Tokyo 5 (1998), no. 1, 119 – 148. · Zbl 0933.14033
[9] A. Cayley. On the theory of elimination. Cambridge and Dublin Math. J. 3 (1848), 116-120.
[10] M. Chardin, The resultant via a Koszul complex, Computational algebraic geometry (Nice, 1992) Progr. Math., vol. 109, Birkhäuser Boston, Boston, MA, 1993, pp. 29 – 39. · Zbl 0827.12003 · doi:10.1007/978-1-4612-2752-6_3
[11] David A. Cox, The homogeneous coordinate ring of a toric variety, J. Algebraic Geom. 4 (1995), no. 1, 17 – 50. · Zbl 0846.14032
[12] David Cox, John Little, and Donal O’Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer-Verlag, New York, 1998. · Zbl 0920.13026
[13] 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. · Zbl 1066.14061
[14] 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.
[15] A. L. Dixon. The Eliminant of three quantics in two independent variables. Proc. London Math. Soc. 6 (1908), 49-69. · JFM 40.0207.01
[16] I. Z. Emiris. Sparse Elimination and Applications in Kinematics. Ph.D. Thesis, University of California at Berkeley, 1994.
[17] 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. CMP 98:10
[18] 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. · Zbl 0943.13005 · doi:10.1006/jsco.1998.0266
[19] 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. · Zbl 0813.14039
[20] I. M. Gel\(^{\prime}\)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.
[21] I. M. Gel\(^{\prime}\)fand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1994. · Zbl 0827.14036
[22] Birkett Huber and Bernd Sturmfels, A polyhedral method for solving sparse polynomial systems, Math. Comp. 64 (1995), no. 212, 1541 – 1555. · Zbl 0849.65030
[23] J. P. Jouanolou, Formes d’inertie et résultant: un formulaire, Adv. Math. 126 (1997), no. 2, 119 – 250 (French). · Zbl 0882.13008 · doi:10.1006/aima.1996.1609
[24] M. M. Kapranov, B. Sturmfels, and A. V. Zelevinsky, Chow polytopes and general resultants, Duke Math. J. 67 (1992), no. 1, 189 – 218. · Zbl 0780.14027 · doi:10.1215/S0012-7094-92-06707-X
[25] T.Krick, L.M. Pardo, and M. Sombra. Sharp estimates for the arithmetic Nullstellensatz. Duke Mathematical Journal, Vol. 109, No. 3, 521-598, 2001. · Zbl 1010.11035
[26] Daniel Lazard, Résolution des systèmes d’équations algébriques, Theoret. Comput. Sci. 15 (1981), no. 1, 77 – 110 (French, with English summary). · Zbl 0459.68013 · doi:10.1016/0304-3975(81)90064-5
[27] F. Macaulay. Some Formulae in Elimination. Proc. London Math. Soc. 1 33, 3-27, 1902. · JFM 34.0195.01
[28] M. Minimair Sparse Resultant under Vanishing Coefficients. Preprint, 2001. Available at http://minimair.org · Zbl 1096.14042
[29] Paul Pedersen and Bernd Sturmfels, Product formulas for resultants and Chow forms, Math. Z. 214 (1993), no. 3, 377 – 396. · Zbl 0792.13006 · doi:10.1007/BF02572411
[30] 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. · Zbl 0798.68073
[31] J. Maurice Rojas, Solving degenerate sparse polynomial systems faster, J. Symbolic Comput. 28 (1999), no. 1-2, 155 – 186. Polynomial elimination — algorithms and applications. · Zbl 0943.65060 · doi:10.1006/jsco.1998.0271
[32] Bernd Sturmfels, Sparse elimination theory, Computational algebraic geometry and commutative algebra (Cortona, 1991) Sympos. Math., XXXIV, Cambridge Univ. Press, Cambridge, 1993, pp. 264 – 298. · Zbl 0837.13011
[33] Bernd Sturmfels, On the Newton polytope of the resultant, J. Algebraic Combin. 3 (1994), no. 2, 207 – 236. · Zbl 0798.05074 · doi:10.1023/A:1022497624378
[34] 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. · Zbl 0916.13008 · doi:10.1090/psapm/053/1602347
[35] Bernd Sturmfels and Andrei Zelevinsky, Multigraded resultants of Sylvester type, J. Algebra 163 (1994), no. 1, 115 – 127. · Zbl 0813.13018 · doi:10.1006/jabr.1994.1007
[36] 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.
[37] Jerzy Weyman and Andrei Zelevinsky, Determinantal formulas for multigraded resultants, J. Algebraic Geom. 3 (1994), no. 4, 569 – 597. · Zbl 0816.13007
[38] 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.