Artículo

Artículo de Acceso Abierto. Puede ser descargado en su versión final
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We present a new algorithm for the computation of resultants associated with multihomogeneous (and, in particular, homogeneous) polynomial equation systems using straight-line programs. Its complexity is polynomial in the number of coefficients of the input system and the degree of the resultant computed. © 2006 Elsevier Ltd. All rights reserved.

Registro:

Documento: Artículo
Título:Computing multihomogeneous resultants using straight-line programs
Autor:Jeronimo, G.; Sabia, J.
Filiación:Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Ciudad Universitaria, 1428 Buenos Aires, Argentina
Departamento de Ciencias Exactas, Ciclo Básico Común, Universidad de Buenos Aires, Ciudad Universitaria, 1428 Buenos Aires, Argentina
Palabras clave:Multihomogeneous system; Poisson-type product formula; Sparse resultant; Symbolic Newton's algorithm
Año:2007
Volumen:42
Número:1-2
Página de inicio:218
Página de fin:235
DOI: http://dx.doi.org/10.1016/j.jsc.2006.03.006
Handle:http://hdl.handle.net/20.500.12110/paper_07477171_v42_n1-2_p218_Jeronimo
Título revista:Journal of Symbolic Computation
Título revista abreviado:J. Symb. Comput.
ISSN:07477171
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_07477171_v42_n1-2_p218_Jeronimo.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_07477171_v42_n1-2_p218_Jeronimo

Referencias:

  • Bernstein, D.N., The number of roots of a system of equations (1975) Funct. Anal. Appl., 9 (3), pp. 183-185
  • Bürgisser, P., Clausen, M., Shokrollahi, M.A., (1997) Algebraic Complexity Theory, , Springer-Verlag
  • Canny, J.F., Emiris, I.Z., An efficient algorithm for the sparse mixed resultant (1993) LNCS, 263, pp. 89-104. , Proc. Int. Symp. on Appl. Algebra, Algebraic Algorithms and Error-Corr. Codes. Cohen G., Mora T., and Moreno O. (Eds). 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) Cambridge and Dublin Math. J., 3, pp. 116-120
  • Cox, D., Little, J., O'Shea, D., (1998) Grad. Texts in Math., 185. , Springer-Verlag
  • D'Andrea, C., Macaulay style formulas for sparse resultants (2002) Trans. Amer. 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
  • Dickenstein, A., Emiris, I.Z., Multihomogeneous resultant formulae by means of complexes (2003) J. Symbolic Comput., 36 (3-4), pp. 317-342
  • Emiris, I.Z., Toric resultants and applications to geometric modelling (2005) Algorithms and Computation in Mathematics, 14. , Solving Polynomial Equations. Foundations, Algorithms, and Applications. Dickenstein A., and Emiris I.Z. (Eds), Springer-Verlag, Berlin
  • Emiris, I.Z., Mourrain, B., Matrices in elimination theory (1999) J. Symbolic Comput., 28 (1-2), pp. 3-44
  • Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V., (1994) Discriminants, Resultants, and Multidimensional Determinants, , Birkhäuser
  • Giusti, M., Heintz, J., Hägele, K., Morais, J.E., Pardo, L.M., Montaña, J.L., Lower bounds for Diophantine approximation (1997) J. Pure Appl. Algebra, 117-118, pp. 277-317
  • 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) Sympos. Math. XXXIV, pp. 216-256. , Computational Algebraic Geometry and Commutative Algebra (Cortona, 1991), Cambridge Univ. Press, Cambridge
  • 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
  • Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. Comput. Sci., 24, pp. 239-277
  • Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A., Deformation techniques for efficient polynomial equation solving (2000) J. Complexity, 16, pp. 70-109
  • Heintz, J., Schnorr, C.-P., Testing polynomials which are easy to compute (1982) Monographie 30 de l'Enseignement Mathématique, pp. 237-254
  • Hodge, W.V.D., Pedoe, D., (1952) Methods of Algebraic Geometry, II. , Cambridge University Press
  • Jeronimo, G., Krick, T., Sabia, J., Sombra, M., The computational complexity of the Chow form (2004) Found. Comput. Math., 4 (1), pp. 41-117
  • Jouanolou, J.P., Le formalisme du résultant (1991) Adv. Math., 90 (2), pp. 117-263
  • Macaulay, F., Some formulae in elimination (1902) Proc. London Math. Soc., 1 (33), pp. 3-27
  • McCoy, N., On the resultant of a system of forms homogeneous in each of several sets of variables (1933) Trans. Amer. Math. Soc., 35 (1), pp. 215-233
  • McLennan, A., The maximum number of real roots of a multihomogeneous system of polynomial equations (1999) Beiträge Algebra Geom., 40 (2), pp. 343-350
  • Minimair, M., Sparse resultant under vanishing coefficients (2003) J. Algebraic Combin., 18 (1), pp. 53-73
  • Morgan, A., Sommese, A., Wampler, C., A product-decomposition bound for Bezout numbers (1995) SIAM J. Numer. Anal., 32 (4), pp. 1308-1325
  • Pedersen, P., Sturmfels, B., Product formulas for resultants and Chow forms (1993) Math. Z., 214, pp. 377-396
  • Shafarevich, I., (1972) Basic Algebraic Geometry, , Springer-Verlag
  • Strassen, V., Vermeidung von Divisionen (1973) J. Reine Angew. Math., 264, pp. 182-202
  • Sturmfels, B., Sparse elimination theory (1993) Sympos. Math. XXXIV, pp. 264-298. , Computational Algebraic Geometry and Commutative Algebra (Cortona, 1991). Eisenbud D., and Robbbiano L. (Eds), Cambridge Univ. Press
  • Sturmfels, B., On the Newton polytope of the resultant (1994) J. Algebraic Combin., 3 (2), pp. 207-236
  • Sturmfels, B., Zelevinsky, A., Multigraded resultants of Sylvester type (1994) J. Algebra, 163, pp. 115-127
  • 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
  • von zur Gathen, J., Parallel arithmetic computations: a survey (1986) LNCS, 33, pp. 93-112. , Proc. 12th FOCS, Bratislava
  • Weyman, J., Zelevinsky, A., Determinantal formulas for multigraded resultants (1994) J. Algebraic Geom., 3 (4), pp. 569-597

Citas:

---------- APA ----------
Jeronimo, G. & Sabia, J. (2007) . Computing multihomogeneous resultants using straight-line programs. Journal of Symbolic Computation, 42(1-2), 218-235.
http://dx.doi.org/10.1016/j.jsc.2006.03.006
---------- CHICAGO ----------
Jeronimo, G., Sabia, J. "Computing multihomogeneous resultants using straight-line programs" . Journal of Symbolic Computation 42, no. 1-2 (2007) : 218-235.
http://dx.doi.org/10.1016/j.jsc.2006.03.006
---------- MLA ----------
Jeronimo, G., Sabia, J. "Computing multihomogeneous resultants using straight-line programs" . Journal of Symbolic Computation, vol. 42, no. 1-2, 2007, pp. 218-235.
http://dx.doi.org/10.1016/j.jsc.2006.03.006
---------- VANCOUVER ----------
Jeronimo, G., Sabia, J. Computing multihomogeneous resultants using straight-line programs. J. Symb. Comput. 2007;42(1-2):218-235.
http://dx.doi.org/10.1016/j.jsc.2006.03.006