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 |
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