Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We present a new probabilistic symbolic algorithm that, given a variety defined in an n-dimensional affine space by a generic sparse system with fixed supports, computes the Zariski closure of its projection to an ℓ-dimensional coordinate affine space with ℓ

Registro:

Documento: Artículo
Título:Elimination for Generic Sparse Polynomial Systems
Autor:Herrero, M.I.; 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
IMAS, CONICET-UBA, Buenos Aires, Argentina
Palabras clave:Algorithms and complexity; Projection of algebraic varieties; Sparse polynomial systems
Año:2014
Volumen:51
Número:3
Página de inicio:578
Página de fin:599
DOI: http://dx.doi.org/10.1007/s00454-014-9571-z
Título revista:Discrete and Computational Geometry
Título revista abreviado:Discrete Comput. Geom.
ISSN:01795376
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01795376_v51_n3_p578_Herrero

Referencias:

  • Adrovic, D., Verschelde, J., Computing Puiseux series for algebraic surfaces (2012) Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation (ISSAC 2012), pp. 20-27. , Grenoble, FranceJuly 22-25, 2012
  • Adrovic, D., Verschelde, J., Polyhedral methods for space curves exploiting symmetry applied to the cyclic n-roots problem (2013) Computer Algebra in Scientific Computing, 15th International Workshop, 8136, pp. 10-29. , CASC 2013Berlin, GermanyLecture Notes in Computer Science, V. P. Gerdt, W. Koepf, E. W. Mayr, and E. V. Vorozhtsov (Eds.)
  • Berkowitz, S.J., On computing the determinant in small parallel time using a small number of processors (1984) Inf. Process. Lett., 18 (3), pp. 147-150
  • Bernstein, D.N., The number of roots of a system of equations (1975) Funct. Anal. Appl., 9, pp. 183-185
  • Bini, D., Pan, V.Y., (1994) Polynomial and Matrix Computations. Vol. 1. Fundamental Algorithms, , Progress in Theoretical Computer Science, Boston: Birkhäuser Boston
  • Bürgisser, P., Clausen, M., Shokrollahi, M.A., (1997) Algebraic Complexity Theory, 315. , Grundlehren Math. Wiss, Berlin: Springer
  • Caniglia, L., How to compute the Chow form of an unmixed polynomial ideal in single exponential time (1990) Appl. Algebra Eng. Commun. Comput., 1 (1), pp. 25-41
  • Canny, J., Emiris, I.Z., A subdivision-based algorithm for the sparse resultant (2000) J. ACM, 47 (3), pp. 417-451
  • Chistov, A.L., Grigor'ev, D.Y., Complexity of quantifier elimination in the theory of algebraically closed fields (1984) Mathematical Foundations of Computer Science, 1984, 176, pp. 17-31. , Prague1984Lecture Notes in Computer Science, Berlin: Springer
  • Cox, D., Little, J., O'Shea, D., (1998) Using Algebraic Geometry, 185. , Grad. Texts Math, New York: Springer
  • D'Alfonso, L., Jeronimo, G., Ollivier, F., Sedoglavic, A., Solernó, P., A geometric index reduction method for implicit systems of differential algebraic equations (2011) J. Symb. Comput., 46 (10), pp. 1114-1138
  • 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. , Effective methods in algebraic geometry (Bath, 2000)
  • Dyer, M., Gritzmann, P., Hufnagel, A., On the complexity of computing mixed volumes (1998) SIAM J. Comput., 27 (2), pp. 356-400
  • Edmonds, J., Submodular functions, matroids, and certain polyhedra (1970) Combinatorial Structures and Their Applications, pp. 69-87. , Proc. Calgary Internat. Conf., Calgary, Alta.1969, New York: Gordon & Breach
  • Emiris, I.Z., Canny, J.F., Efficient incremental algorithms for the sparse resultant and the mixed volume (1995) J. Symb. Comput., 20 (2), pp. 117-149
  • Emiris, I.Z., Verschelde, J., How to count efficiently all affine roots of a polynomial system (1999) Discrete Appl. Math., 93 (1), pp. 21-32. , 13th European Workshop on Computational Geometry CG'97 (Würzburg, 1997)
  • Fitchas, N., Galligo, A., Morgenstern, J., Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields (1990) J. Pure Appl. Algebra, 67 (1), pp. 1-14
  • Gao, T., Li, T.Y., Mixed volume computation for semi-mixed systems (2003) Discrete Comput. Geom., 29 (2), pp. 257-277
  • Gao, T., Li, T.Y., Wang, X., Finding all isolated zeroes of polynomial systems in ℂn via stable mixed volumes. Polynomial elimination-algorithms and applications (1999) J. Symb. Comput., 28 (1-2), pp. 187-211
  • Giusti, M., Heintz, J., Algorithmes-disons rapides-pour la décomposition d'une variété algébrique en composantes irréductibles et équidimensionelles (1991) Proc. Effective Methods in Algebraic Geometry, 94, pp. 169-194. , Castiglioncello1990Progr. Math, Boston: Birkhäuser Boston
  • Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complex., 17 (1), pp. 154-211
  • Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theor. Comput. Sci., 24 (3), pp. 239-277
  • Herrero, M.I., Jeronimo, G., Sabia, J., Computing isolated roots of sparse polynomial systems in affine space (2010) Theor. Comput. Sci., 411 (44-46), pp. 3894-3904
  • Herrero, M.I., Jeronimo, G., Sabia, J., Affine solution sets of sparse polynomial systems (2013) J. Symb. Comput., 51, pp. 34-54
  • Huber, B., Sturmfels, B., A polyhedral method for solving sparse polynomial systems (1995) Math. Comput., 64 (212), pp. 1541-1555
  • Huber, B., Sturmfels, B., Bernstein's theorem in affine space (1997) Discrete Comput. Geom., 17 (2), pp. 137-141
  • Jeronimo, G., Sabia, J., Computing multihomogeneous resultants using straight-line programs (2007) J. Symb. Comput., 42 (1-2), pp. 218-235
  • 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
  • Khovanskii, A.G., Newton polyhedra and toroidal varieties (1978) Funct. Anal. Appl., 11, pp. 289-296
  • Kushnirenko, A.G., Newton polytopes and the Bézout theorem (1976) Funct. Anal. Appl., 10, pp. 233-235
  • Li, T.Y., Li, X., Finding mixed cells in the mixed volume computation (2001) Found. Comput. Math., 1 (2), pp. 161-181
  • Li, T.Y., Wang, X., The BKK root count in ℂn (1996) Math. Comput., 65 (216), pp. 1477-1484
  • Mizutani, T., Takeda, A., Kojima, M., Dynamic enumeration of all mixed cells (2007) Discrete Comput. Geom., 37 (3), pp. 351-367
  • Puddu, S., Sabia, J., An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs (1998) J. Pure Appl. Algebra, 129 (2), pp. 173-200
  • Rojas, J.M., A convex geometrical approach to counting the roots of a polynomial system (1994) Theor. Comput. Sci., 133 (1), pp. 105-140
  • Rojas, J.M., Why polyhedra matter in non-linear equation solving (2003) Topics in Algebraic Geometry and Geometric Modeling, 334, pp. 293-320. , Contemp. Math, Providence: Am. Math. Soc
  • Rojas, J.M., Wang, X., Counting affine roots of polynomial systems via pointed Newton polytopes (1996) J. Complex., 12 (2), pp. 116-133
  • Schost, É., 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
  • Steffens, R., Theobald, T., Mixed volume techniques for embeddings of Laman graphs (2010) J. Comput. Geom., 43 (2), pp. 84-93
  • Sturmfels, B., On the Newton polytope of the resultant (1994) J. Algebr. Comb., 3 (2), pp. 207-236
  • Tarski, A., (1951) A Decision Method for Elementary Algebra and Geometry, , 2nd edn., Berkeley/Los Angeles: University of California Press
  • Verschelde, J., Polyhedral methods in numerical algebraic geometry (2009) Interactions of Classical and Numerical Algebraic Geometry, 496, pp. 243-263. , Contemp. Math, Providence: Am. Math. Soc
  • Verschelde, J., Verlinden, P., Cools, R., Homotopies exploiting Newton polytopes for solving sparse polynomial systems (1994) SIAM J. Numer. Anal., 31 (3), pp. 915-930
  • Verschelde, J., Gatermann, K., Cools, R., Mixed-volume computation by dynamic lifting applied to polynomial system solving (1996) Discrete Comput. Geom., 16 (1), pp. 69-112
  • von zur Gathen, J., Gerhard, J., (1999) Modern Computer Algebra, , Cambridge: Cambridge University Press
  • Zippel, R., (1993) Effective Polynomial Computation, 241. , Kluwer Int. Ser. Eng. Comput. Sci, Dordrecht: Kluwer

Citas:

---------- APA ----------
Herrero, M.I., Jeronimo, G. & Sabia, J. (2014) . Elimination for Generic Sparse Polynomial Systems. Discrete and Computational Geometry, 51(3), 578-599.
http://dx.doi.org/10.1007/s00454-014-9571-z
---------- CHICAGO ----------
Herrero, M.I., Jeronimo, G., Sabia, J. "Elimination for Generic Sparse Polynomial Systems" . Discrete and Computational Geometry 51, no. 3 (2014) : 578-599.
http://dx.doi.org/10.1007/s00454-014-9571-z
---------- MLA ----------
Herrero, M.I., Jeronimo, G., Sabia, J. "Elimination for Generic Sparse Polynomial Systems" . Discrete and Computational Geometry, vol. 51, no. 3, 2014, pp. 578-599.
http://dx.doi.org/10.1007/s00454-014-9571-z
---------- VANCOUVER ----------
Herrero, M.I., Jeronimo, G., Sabia, J. Elimination for Generic Sparse Polynomial Systems. Discrete Comput. Geom. 2014;51(3):578-599.
http://dx.doi.org/10.1007/s00454-014-9571-z