Artículo

El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We prove that the sparse resultant, redefined by D'Andrea and Sombra and by Esterov as a power of the classical sparse resultant, can be evaluated in a number of steps which is polynomial in its degree, its number of variables and the size of the exponents of the monomials in the Laurent polynomials involved in its definition. Moreover, we design a probabilistic algorithm of this order of complexity to compute a straight-line program that evaluates it within this number of steps. © 2017 Elsevier Ltd

Registro:

Documento: Artículo
Título:Sparse resultants and straight-line programs
Autor:Jeronimo, G.; Sabia, J.
Filiación:Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Matemática, Buenos Aires, Argentina
Universidad de Buenos Aires, Ciclo Básico Común, Departamento de Ciencias Exactas, Buenos Aires, Argentina
CONICET–Universidad de Buenos Aires, Instituto de Investigaciones Matemáticas Luis A, Santaló (IMAS), Buenos Aires, Argentina
Palabras clave:Algorithms; Sparse resultants; Straight-line programs
Año:2018
Volumen:87
Página de inicio:14
Página de fin:27
DOI: http://dx.doi.org/10.1016/j.jsc.2017.05.005
Título revista:Journal of Symbolic Computation
Título revista abreviado:J. Symb. Comput.
ISSN:07477171
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_07477171_v87_n_p14_Jeronimo

Referencias:

  • Bernstein, D.N., The number of roots of a system of equations (1975) Funct. Anal. Appl., 9 (3), pp. 183-185
  • Bézout, E., Théorie Générale des Équations Algébriques (1779), Paris; Bürgisser, B., Clausen, M., Shokrollahi, M.A., Algebraic Complexity Theory (1997), Springer-Verlag; Canny, J.F., Emiris, I.Z., An efficient algorithm for the sparse mixed resultant (1993) Proc. Int. Symp. on Appl. Algebra, Algebraic Algorithms and Error-Corr. Codes, LNCS, 673, pp. 89-104. , G. Cohen T. Mora O. Moreno Puerto Rico
  • Canny, J.F., Emiris, I.Z., A subdivision-based algorithm for the sparse resultant (2000) J. ACM, 47 (3), pp. 417-451
  • Cayley, A., On the theory of elimination (1848) Camb. Dublin Math. J., 3, pp. 116-120
  • Cox, D., Little, J., O'Shea, D., Using Algebraic Geometry (2005) Graduate Texts in Mathematics, 185. , second edition Springer-Verlag New York
  • D'Andrea, C., Macaulay style formulas for sparse resultants (2002) Trans. Am. Math. Soc., 354 (7), pp. 2595-2629
  • D'Andrea, C., Dickenstein, A., Explicit formulas for the multivariate resultant (2001) J. Pure Appl. Algebra, 164 (1-2), pp. 59-86
  • D'Andrea, C., Jeronimo, G., Sombra, M., in preparation. Sparse resultants: combinatorial properties and Macaulay style formulas; D'Andrea, C., Sombra, M., A Poisson formula for the sparse resultant (2015) Proc. Lond. Math. Soc. (3), 110 (4), pp. 932-964
  • Dyer, M., Gritzmann, P., Hufnagel, A., On the complexity of computing mixed volumes (1998) SIAM J. Comput., 27 (2), pp. 356-400
  • Emiris, I.Z., Mourrain, B., Matrices in elimination theory (1999) J. Symb. Comput., 28, pp. 3-44
  • Esterov, A., Newton polyhedra of discriminants of projections (2010) Discrete Comput. Geom., 44 (1), pp. 96-148
  • Ewald, G., Combinatorial Convexity and Algebraic Geometry (1996) Grad. Texts in Math., 168. , Springer New York
  • von zur Gathen, J., Gerhard, J., Modern Computer Algebra (1999), Cambridge University Press New York; Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V., Discriminants, Resultants, and Multidimensional Determinants. Mathematics: Theory & Applications (1994), Birkhäuser Boston, Inc. Boston, MA; Giusti, M., Heintz, J., La détermination des points isolés et de la dimension d'une variété algébrique peut se faire en temps polynomial (1993) Computational Algebraic Geometry and Commutative Algebra, Cortona, 1991, Sympos. Math., vol. XXXIV, pp. 216-256. , Cambridge Univ. Press Cambridge
  • Giusti, M., Heintz, J., Hägele, K., Morais, J.E., Pardo, L.M., Montaña, J.L., Lower bounds for Diophantine approximations (1997) J. Pure Appl. Algebra, 117/118, pp. 277-317. , Algorithms for Algebra, Eindhoven, 1996
  • Giusti, M., Heintz, J., Morais, J.E., Morgenstern, J., Pardo, L.M., Straight-line programs in geometric elimination theory (1998) J. Pure Appl. Algebra, 124 (1-3), pp. 101-146
  • Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complex., 17 (1), pp. 154-211
  • Grenet, B., Koiran, P., Portier, N., On the complexity of the multivariate resultant (2013) J. Complex., 29, pp. 142-157
  • Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A., Deformation techniques for efficient polynomial equation solving (2000) J. Complex., 16, pp. 70-109
  • Heintz, J., Schnorr, C.P., Testing polynomials which are easy to compute (1982) Monogr. Enseign. Math., 30, pp. 237-254
  • Jeronimo, G., Krick, T., Sabia, J., Sombra, M., The computational complexity of the Chow form (2004) Found. Comput. Math., 4 (1), pp. 41-117
  • Jeronimo, G., Matera, G., Solernó, P., Waissbein, A., Deformation techniques for sparse systems (2009) Found. Comput. Math., 9 (1), pp. 1-50
  • Jeronimo, G., Sabia, J., Computing multihomogeneous resultants using straight-line programs (2007) J. Symb. Comput., 42, pp. 218-235
  • Kaltofen, E., Villard, G., On the complexity of computing determinants (2004) Comput. Complex., 13 (3-4), pp. 91-130
  • Kaltofen, E., Koiran, P., Expressing a fraction of two determinants as a determinant (2008) Proceedings ISSAC 2008, pp. 141-146
  • Lecerf, G., Geomsolvex, a Mathemagix library for geometric polynomial system solving (2012), http://www.mathemagix.org/www/geomsolvex/doc/html/index.en.html; Macaulay, F., Some formulae in elimination (1902) Proc. Lond. Math. Soc., 1 (33), pp. 3-27
  • Minimair, M., Sparse resultant under vanishing coefficients (2003) J. Algebraic Comb., 18, pp. 53-73
  • Oka, M., Non-degenerate Complete Intersection Singularity (1997) Actualités Mathématiques, , Hermann Paris
  • Pedersen, P., Sturmfels, B., Product formulas for resultants and Chow forms (1993) Math. Z., 214 (3), pp. 377-396
  • Schost, E., Computing parametric geometric resolutions (2003) Appl. Algebra Eng. Commun. Comput., 13 (5), pp. 349-393
  • Schwartz, J., Fast probabilistic algorithms for verification of polynomial identities (1980) J. ACM, 27, pp. 701-717
  • Storjohann, A., Algorithms for Matrix Canonical Forms (2000), Ph.D. thesis ETH Zürich, Switzerland; Strassen, V., Vermeidung von Divisionen (1973) J. Reine Angew. Math., 264, pp. 184-202
  • Sturmfels, B., Sparse elimination theory (1993) Computational Algebraic Geometry and Commutative Algebra, Sympos. Math. XXXIV, 41, pp. 264-298. , D. Eisenbud L. Robbbiano Cortona, 1991 Cambridge Univ. Press
  • Sturmfels, B., On the Newton polytope of the resultant (1994) J. Algebraic Comb., 3 (2), pp. 207-236
  • Sylvester, J.J., 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 (1853) Philos. Trans., 143, pp. 407-548
  • Zippel, R., Effective Polynomial Computation (1993) Kluwer Int. Ser. Eng. Comput. Sci., 241. , Kluwer Dordrecht

Citas:

---------- APA ----------
Jeronimo, G. & Sabia, J. (2018) . Sparse resultants and straight-line programs. Journal of Symbolic Computation, 87, 14-27.
http://dx.doi.org/10.1016/j.jsc.2017.05.005
---------- CHICAGO ----------
Jeronimo, G., Sabia, J. "Sparse resultants and straight-line programs" . Journal of Symbolic Computation 87 (2018) : 14-27.
http://dx.doi.org/10.1016/j.jsc.2017.05.005
---------- MLA ----------
Jeronimo, G., Sabia, J. "Sparse resultants and straight-line programs" . Journal of Symbolic Computation, vol. 87, 2018, pp. 14-27.
http://dx.doi.org/10.1016/j.jsc.2017.05.005
---------- VANCOUVER ----------
Jeronimo, G., Sabia, J. Sparse resultants and straight-line programs. J. Symb. Comput. 2018;87:14-27.
http://dx.doi.org/10.1016/j.jsc.2017.05.005