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