Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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

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.


References [Enhancements On Off] (What's this?)

  • [AS] W. Auzinger and H.J. Stetter. An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations. In Proc. Intern. Conf. on Numerical Math., Intern. Series of Numerical Math., 86, pages 11-30. Birkhäuser Verlag, Basel, 1988. MR 91g:65112
  • [Bez] E. Bézout. Théorie Générale des Équations Algébriques. Paris, 1779.
  • [Ber] D. N. Bernstein.The Number of Roots of a System of Equations. Functional Anal. Appl. 9 (1975), 183-185. MR 55:8034
  • [Can1] J.F. Canny. The Complexity of Robot Motion Planning. M.I.T. Press, Cambridge, Mass., 1988. MR 89m:68142
  • [Can2] J.F. Canny. Generalised Characteristic Polynomials. J. Symbolic Computation, 9: 241-250, 1990. MR 91i:13030
  • [CE1] J. F. Canny and I. Z. Emiris. An Efficient Algorithm for the Sparse Mixed Resultant. In Cohen, G., Mora, T. and Moreno, O., eds, Proc. Int. Symp. on Appl. Algebra, Algebraic Algorithms and Error-Corr. Codes, Puerto Rico, LNCS 263, (1993), 89-104. Berlin, Springer Verlag. MR 94m:12010
  • [CE2] 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
  • [CDS] E. Cattani, A. Dickenstein and B. Sturmfels. Residues and Resultants. J. Math. Sci. Univ. Tokyo, 5:119-148, 1998. MR 2000b:14065
  • [Cay] A. Cayley. On the theory of elimination. Cambridge and Dublin Math. J. 3 (1848), 116-120.
  • [Cha] 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. MR 94f:12002
  • [Cox] D. Cox. The Homogeneous Coordinate Ring of a Toric Variety. J.Algebr.Geom., 4,17-50 (1995). MR 95i:14046
  • [CLO] D. Cox, J. Little and D. O'Shea. Using Algebraic Geometry. Number 185 in Graduate Texts in Mathematics. Springer-Verlag, New York, 1998. MR 99h:13033
  • [DD] 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.
  • [Dem] 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.
  • [Dix] A. L. Dixon. The Eliminant of three quantics in two independent variables. Proc. London Math. Soc. 6 (1908), 49-69.
  • [Emi1] I. Z. Emiris. Sparse Elimination and Applications in Kinematics. Ph.D. Thesis, University of California at Berkeley, 1994.
  • [Emi2] 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
  • [EM] I. .Z. Emiris and B. Mourrain. Matrices in Elimination Theory. J. Symbolic Computation 28, No. 1/2 (1999), 3-44. MR 2000h:68249
  • [Ful] W. Fulton. Introduction to Toric Varieties, Ann. of Math. Studies, no. 131, Princeton, NJ, Princeton University Press (1993). MR 94g:14028
  • [GKZ1] I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinski. Discriminants of polynomials in several variables and triangulations of Newton polytopes. Leningrad Math. J., 2(3), (1991), 449-505. MR 91m:14080
  • [GKZ2] I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinski. Discriminants, Resultants and Multidimensional Determinants, Birkhäuser, Boston-Basel-Berlin, 1994. MR 95e:14045
  • [HS] B. Huber and B. Sturmfels. A Polyhedral Method for Solving Sparse Polynomial Systems. Math. Comput.,64 1542-1555. MR 95m:65100
  • [Jou] J. P. Jouanolou. Formes d'inertie et résultant: un formulaire. Advances in Mathematics 126 (1997), 119-250. MR 98k:14002
  • [KSZ] M. Kapranov, B. Sturmfels and A. Zelevinsky. Chow Polytopes and General Resultants. Duke Mathematical Journal, Vol. 67, No. 1, 189-217, 1992. MR 93e:14062
  • [KPS] T.Krick, L.M. Pardo, and M. Sombra. Sharp estimates for the arithmetic Nullstellensatz. Duke Mathematical Journal, Vol. 109, No. 3, 521-598, 2001.
  • [Laz] D. Lazard. Résolution des Systèmes d' Équations algebriques. Theor. Comp. Science, 15: 77-110, 1981. MR 82i:12001
  • [Mac] F. Macaulay. Some Formulae in Elimination. Proc. London Math. Soc. 1 33, 3-27, 1902.
  • [Min] M. Minimair Sparse Resultant under Vanishing Coefficients. Preprint, 2001. Available at http://minimair.org
  • [PS] P. Pedersen and B. Sturmfels. Product Formulas for Resultants and Chow Forms. Mathematische Zeitschrift, 214 (1993), 377-396. MR 94m:14068
  • [Ren] 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. MR 93h:03011
  • [Roj] J.M.Rojas. Solving Degenerate Sparse Polynomial Systems Faster. J. Symbolic Computation (1999) 28, 155-186. MR 2000g:65050
  • [Stu1] B. Sturmfels. Sparse Elimination Theory. In D. Eisenbud and L. Robbiano, editors, Computation Algebraic Geometry and Commutative Algebra, Proceedings, Cortona, June 1991. Cambridge University Press, pages 264-298. MR 94k:13035
  • [Stu2] B. Sturmfels. On The Newton Polytope of the Resultant. Journal of Algebraic Combinatorics, 3 (1994), 207-236. MR 95j:52024
  • [Stu3] B. Sturmfels. Introduction to Resultants. In Applications of Computational Algebraic Geometry, San Diego, January 1997, Proc. Sympos. Appl. Math., vol. 53, Amer. Math. Soc., Providence, RI, 1998, pages 25-39. MR 99a:13015
  • [SZ] B. Sturmfels and A. Zelevinsky. Multigraded Resultants of Sylvester Type. J. of Algebra, 163(1):115-127, 1994. MR 95i:14050
  • [Syl] 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.
  • [WZ] J. Weyman and A. Zelevinsky. Determinantal formulas for multigraded resultants. J. Algebraic Geometry 3 (1994), 569-597. MR 95j:14074
  • [ZCG] 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.

Similar Articles

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
Email: cdandrea@dm.uba.ar

DOI: https://doi.org/10.1090/S0002-9947-02-02910-0
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

American Mathematical Society