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