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:

This paper focuses on the equidimensional decomposition of affine varieties defined by sparse polynomial systems. For generic systems with fixed supports, we give combinatorial conditions for the existence of positive dimensional components which characterize the equidimensional decomposition of the associated affine variety. This result is applied to design an equidimensional decomposition algorithm for generic sparse systems. For arbitrary sparse systems of n polynomials in n variables with fixed supports, we obtain an upper bound for the degree of the affine variety defined and we present an algorithm which computes finite sets of points representing its equidimensional components. © 2012 Elsevier B.V.

Registro:

Documento: Artículo
Título:Affine solution sets of sparse polynomial systems
Autor:Herrero, M.I.; Jeronimo, G.; Sabia, J.
Filiación:Departamento de Matemática, Facultad de Ciencias Exactasy Naturales, Universidad de Buenos Aires, Ciudad Universitaria, (1428) Buenos Aires, Argentina
Departamento de Matemática and IMAS, UBA-CONICET, Facultad de Ciencias Exactasy Naturales, Universidad de Buenos Aires, Ciudad Universitaria, (1428) Buenos Aires, Argentina
Departamento de Ciencias Exactas, Ciclo Básico Común, Universidad de Buenos Aires and IMAS, UBA-CONICET, Ciudad Universitaria, (1428) Buenos Aires, Argentina
Palabras clave:Algorithms and complexity; Degree of affine varieties; Equidimensional decomposition of algebraic varieties; Sparse polynomial systems
Año:2013
Volumen:51
Página de inicio:34
Página de fin:54
DOI: http://dx.doi.org/10.1016/j.jsc.2012.03.006
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_v51_n_p34_Herrero

Referencias:

  • Bernstein, D.N., The number of roots of a system of equations (1975) Funct. Anal. Appl., 9, pp. 183-185
  • Bürgisser, P., Clausen, M., Shokrollahi, M.A., Algebraic Complexity Theory (1997) Grundlehren Math. Wiss., 315. , Springer, Berlin
  • Cattani, E., Dickenstein, A., Counting solutions to binomial complete intersections (2007) J. Complexity, 23 (1), pp. 82-107
  • Chistov, A.L., Grigoriev, D.Y., (1983), Subexponential time solving systems of algebraic equations. LOMI preprint E-9-83, E-10-83. Steklov Institute, Leningrad; Cox, D., Little, J., O'Shea, D., Using Algebraic Geometry (1998) Grad. Texts in Math., 185. , Springer, New York
  • Elkadi, M., Mourrain, B., A new algorithm for the geometric decomposition of a variety (1999) Proceedings of ISSAC'99, pp. 9-16. , ACM, New York, (electronic)
  • 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
  • Gao, T., Li, T.Y., Wang, X., Finding all isolated zeros of polynomial systems in Cn via stable mixed volumes (1999) J. Symbolic Comput., 28 (1-2), pp. 187-211. , Polynomial Elimination-Algorithms and Applications
  • von zur Gathen, J., Gerhard, J., (1999) Modern Computer Algebra, , Cambridge University Press, Cambridge
  • Gianni, P., Trager, B., Zacharias, G., Gröbner bases and primary decomposition of polynomial ideals (1988) J. Symbolic Comput., 6 (2-3), pp. 149-167. , Computational Aspects of Commutative Algebra
  • Giusti, M., Heintz, J., Algorithmes - disons rapides - pour la décomposition d'une variété algébrique en composantes irréductibles et équidimensionelles (1991) Progr. Math., 94, pp. 169-194. , Birkhäuser Boston, Boston, MA, Proc. Effective Methods in Algebraic Geometry
  • 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. Complexity, 17 (1), pp. 154-211
  • Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. 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) Theoret. Comput. Sci., 411 (44-46), pp. 3894-3904
  • Huber, B., Sturmfels, B., A polyhedral method for solving sparse polynomial systems (1995) Math. Comp., 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., 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., Effective equidimensional decomposition of affine varieties (2002) J. Pure Appl. Algebra, 169 (2-3), pp. 229-248
  • Khovanskii, A.G., Newton polyhedra and toroidal varieties (1978) Funct. Anal. Appl., 11, pp. 289-296
  • Krick, T., Pardo, L.M., Sombra, M., Sharp estimates for the arithmetic Nullstellensatz (2001) Duke Math. J., 109 (3), pp. 521-598
  • Kushnirenko, A.G., Newton polytopes and the Bézout theorem (1976) Funct. Anal. Appl., 10, pp. 233-235
  • Lecerf, G., Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers (2003) J. Complexity, 19 (4), pp. 564-596
  • Li, T.Y., Wang, X., The BKK root count in Cn (1996) Math. Comp., 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
  • Rojas, J.M., A convex geometrical approach to counting the roots of a polynomial system (1994) Theoret. Comput. Sci., 133 (1), pp. 105-140
  • Rojas, J.M., Why polyhedra matter in non-linear equation solving (2003) Contemp. Math., 334, pp. 293-320. , Amer. Math. Soc., Providence, RI, Topics in Algebraic Geometry and Geometric Modeling
  • Rojas, J.M., Wang, X., Counting affine roots of polynomial systems via pointed Newton polytopes (1996) J. Complexity, 12 (2), pp. 116-133
  • Rouillier, F., Solving zero-dimensional systems through the rational univariate representation (1999) Appl. Algebra Eng. Commun. Comput., 9 (5), pp. 433-461
  • 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
  • Sommese, A., Wampler, C., Numerical algebraic geometry (1996) Lectures in Appl. Math., 32, pp. 749-763. , Amer. Math. Soc., Providence, RI, The Mathematics of Numerical Analysis
  • Sommese, A.J., Wampler, C.W., (2005) The Numerical Solution of Systems of Polynomials Arising in Engineering and Science, , World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ
  • Sturmfels, B., On the Newton polytope of the resultant (1994) J. Algebraic Combin., 3 (2), pp. 207-236
  • Verschelde, J., Polyhedral methods in numerical algebraic geometry (2009) Contemp. Math., 496, pp. 243-263. , Amer. Math. Soc., Providence, RI, Interactions of Classical and Numerical Algebraic Geometry
  • 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
  • Zippel, R., Effective Polynomial Computation (1993) Kluwer Int. Ser. Eng. Comput. Sci., 241. , Kluwer, Dordrecht

Citas:

---------- APA ----------
Herrero, M.I., Jeronimo, G. & Sabia, J. (2013) . Affine solution sets of sparse polynomial systems. Journal of Symbolic Computation, 51, 34-54.
http://dx.doi.org/10.1016/j.jsc.2012.03.006
---------- CHICAGO ----------
Herrero, M.I., Jeronimo, G., Sabia, J. "Affine solution sets of sparse polynomial systems" . Journal of Symbolic Computation 51 (2013) : 34-54.
http://dx.doi.org/10.1016/j.jsc.2012.03.006
---------- MLA ----------
Herrero, M.I., Jeronimo, G., Sabia, J. "Affine solution sets of sparse polynomial systems" . Journal of Symbolic Computation, vol. 51, 2013, pp. 34-54.
http://dx.doi.org/10.1016/j.jsc.2012.03.006
---------- VANCOUVER ----------
Herrero, M.I., Jeronimo, G., Sabia, J. Affine solution sets of sparse polynomial systems. J. Symb. Comput. 2013;51:34-54.
http://dx.doi.org/10.1016/j.jsc.2012.03.006