Artículo

Jeronimo, G.; Matera, G.; Solernó, P.; Waissbein, A. "Deformation techniques for sparse systems" (2009) Foundations of Computational Mathematics. 9(1):1-50
La versión final de este artículo es de uso interno de la institución.
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We exhibit a probabilistic symbolic algorithm for solving zero-dimensional sparse systems. Our algorithm combines a symbolic homotopy procedure, based on a flat deformation of a certain morphism of affine varieties, with the polyhedral deformation of Huber and Sturmfels. The complexity of our algorithm is cubic in the size of the combinatorial structure of the input system. This size is mainly represented by the cardinality and mixed volume of Newton polytopes of the input polynomials and an arithmetic analogue of the mixed volume associated to the deformations under consideration. © 2008 SFoCM.

Registro:

Documento: Artículo
Título:Deformation techniques for sparse systems
Autor:Jeronimo, G.; Matera, G.; Solernó, P.; Waissbein, A.
Filiación:Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Ciudad Universitaria, Pabellón I, 1428, Buenos Aires, Argentina
National Council of Science and Technology (CONICET), Buenos Aires, Argentina
Instituto de Desarrollo Humano, Universidad Nacional de General Sarmiento, J.M. Gutiérrez 1150, 1613 Los Polvorines, Buenos Aires, Argentina
CoreLabs, CORE Security Technologies, Humboldt 1967, Buenos Aires C1414CTU, Argentina
Doctorado en Ingeniería, Instituto Tecnológico de Buenos Aires, Av. Eduardo Madero 399, Buenos Aires C1106ACD, Argentina
Palabras clave:Complexity; Geometric solutions; Mixed volume; Newton-Hensel lifting; Non-Archimedean height; Polyhedral deformations; Probabilistic algorithms; Puiseux expansions of space curves; Sparse system solving; Symbolic homotopy algorithms; Complexity; Homotopy algorithms; Mixed volume; Newton-Hensel lifting; Non-Archimedean height; Probabilistic algorithm; Space curve; Sparse systems; Algorithms; Deformation
Año:2009
Volumen:9
Número:1
Página de inicio:1
Página de fin:50
DOI: http://dx.doi.org/10.1007/s10208-008-9024-2
Título revista:Foundations of Computational Mathematics
Título revista abreviado:Found. Comput. Math.
ISSN:16153375
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v9_n1_p1_Jeronimo

Referencias:

  • Allgower, E.L., Georg, K., (1990) Numerical Continuation Methods: An Introduction Springer Ser. Comput. Math., 13. , Springer New York
  • Alonso, M.E., Becker, E., Roy, M.-F., Wörmann, T., Zeros, multiplicities and idempotents for zero-dimensional systems (1996) Algorithms in Algebraic Geometry and Applications, Proceedings of MEGA'94 Prog. Math., 143, pp. 1-15. , Birkhäuser Boston
  • Balcázar, J.L., Díaz, J., Gabarró, J., (1988) Structural Complexity i Monogr. Theor. Comput. Sci. EATCS Ser., 11. , Springer Berlin
  • Baur, W., Strassen, V., The complexity of partial derivatives (1983) Theor. Comput. Sci., 22, pp. 317-330
  • Bernstein, D.N., The number of roots of a system of equations (1975) Funct. Anal. Appl., 9, pp. 183-185
  • Bini, D., Pan, V., (1994) Polynomial and Matrix Computations Progress in Theoretical Computer Science, , Birkhäuser Boston
  • Blum, L., Cucker, F., Shub, M., Smale, S., (1998) Complexity and Real Computation, , Springer New York
  • Bompadre, A., Matera, G., Wachenchauzer, R., Waissbein, A., Polynomial equation solving by lifting procedures for ramified fibers (2004) Theoret. Comput. Sci., 315, pp. 335-369. , 2-3
  • Bostan, A., Lecerf, G., Schost, E., Sendra, J.R., Tellegen's principle into practice (2003) Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'03) Philadelphia, PA 3-6 August 2003, pp. 37-44. , ACM Press New York
  • Bostan, A., Schost, E., Polynomial evaluation and interpolation on special sets of points (2005) J. Complexity, 21, pp. 420-446. , 4
  • Bürgisser, P., Clausen, M., Shokrollahi, M.A., (1997) Algebraic Complexity Theory Grundlehren Math. Wiss., 315. , Springer Berlin
  • Cafure, A., Matera, G., Waissbein, A., Seroussi, G., Viola, A., Inverting bijective polynomial maps over finite fields (2006) Proceedings of the 2006 Information Theory Workshop, ITW2006 Punta Del Este, Uruguay 13-17 March 2006, pp. 27-31. , IEEE Information Theory Society New York
  • Castro, D., Giusti, M., Heintz, J., Matera, G., Pardo, L.M., The hardness of polynomial equation solving (2003) Found. Comput. Math., 3, pp. 347-420. , 4
  • Cox, D., Little, J., O'Shea, D., (1998) Using Algebraic Geometry Grad. Texts in Math., 185. , Springer New York
  • Dedieu, J.-P., Cucker, F., Shub, M., Condition number analysis for sparse polynomial systems (1997) Foundations of Computational Mathematics Rio de Janeiro 1997, pp. 267-276. , Springer Berlin
  • Durvye, C., Lecerf, G., A concise proof of the Kronecker polynomial system solver from scratch (2006) Exp. Math., , in press. doi: 10.1016/j.expmath.2007.07.001
  • Emiris, I.Z., Canny, J., Efficient incremental algorithms for the sparse resultant and the mixed volume (1995) J. Symb. Comput., 20, pp. 117-149
  • Ewald, G., (1996) Combinatorial Convexity and Algebraic Geometry Grad. Texts in Math., 168. , Springer New York
  • Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V., (1994) Discriminants, Resultants, and Multidimensional Determinants, , Birkhäuser Boston
  • Giusti, M., Hägele, K., Heintz, J., Morais, J.E., Montaña, J.L., Pardo, L.M., Lower bounds for Diophantine approximation (1997) J. Pure Appl. Algebra, 117-118, pp. 277-317
  • 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, pp. 101-146
  • Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complex., 17, pp. 154-211. , 1
  • Heintz, J., Huguet, L., Poli, A., On the computational complexity of polynomials and bilinear maps (1989) Proceedings of the 5th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-5 Menorca, Spain 15-19 June 1987 Lecture Notes in Comput. Sci., 356, pp. 269-300. , Springer Berlin
  • J. Heintz, Intersection theory and deformation algorithms (2002) The Multihomogeneous Case, , Manuscript, Universidad de Buenos Aires
  • Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A., Deformation techniques for efficient polynomial equation solving (2000) J. Complex., 16, pp. 70-109. , 1
  • Huber, B., Sturmfels, B., A polyhedral method for solving sparse polynomial systems (1995) Math. Comput., 64, pp. 1541-1555. , 212
  • Huber, B., Sturmfels, B., Bernstein's theorem in affine space (1997) Discrete Comput. Geom., 17, pp. 137-141
  • Jeronimo, G., Krick, T., Sabia, J., Sombra, M., The computational complexity of the Chow form (2004) Found. Comput. Math., 4, pp. 41-117. , 1
  • Khovanski, A.G., Newton polyhedra and the genus of complete intersections (1978) Funct. Anal. Appl., 12, pp. 38-46
  • Kushnirenko, A.G., Newton polytopes and the Bézout theorem (1976) Funct. Anal. Appl., 10, pp. 233-235
  • Lecerf, G., Quadratic Newton iteration for systems with multiplicity (2002) Found. Comput. Math., 2, pp. 247-293. , 3
  • Lecerf, G., Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers (2003) J. Complex., 19, pp. 564-596. , 4
  • Li, T.-Y., Li, X., Finding mixed cells in the mixed volume computation (2001) Found. Comput. Math., 1, pp. 161-181. , 2
  • Li, T.Y., Numerical solution of multivariate polynomial systems by homotopy continuation methods (1997) Acta Numer., 6, pp. 399-436
  • Li, T.Y., Wang, X., The BKK root count in n (1996) Math. Comput., 65, pp. 1477-1484. , 216
  • Malajovich, G., Rojas, J.M., High probability analysis of the condition number of sparse polynomial systems (2004) Theor. Comput. Sci., 315, pp. 525-555. , 2-3
  • Morgan, A., (1987) Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems, , Prentice-Hall Englewood Cliffs
  • Morgan, A., Sommese, A., Wampler, C., A generic product-decomposition formula for Bézout numbers (1995) SIAM J. Numer. Anal., 32, pp. 1308-1325
  • Oka, M., (1997) Non-Degenerate Complete Intersection Singularity, , Hermann Paris
  • Pardo, L.M., Cohen, G., Giusti, M., Mora, T., How lower and upper complexity bounds meet in elimination theory (1995) Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings of AAECC-11 Lecture Notes in Comput. Sci., 948, pp. 33-69. , Springer Berlin
  • Pardo, L.M., San Martín, J., Deformation techniques to solve generalized Pham systems (2004) Theoret. Comput. Sci., 315, pp. 593-625. , 2-3
  • Pedersen, P., Sturmfels, B., Product formulas for resultants and Chow forms (1993) Math. Z., 214, pp. 377-396. , 3
  • Philippon, P., Sombra, M., Hauteur normalisée des variétés toriques projectives (2003) J. Inst. Math. Jussieu, , in press. doi: 10.1017/S1474748007000138,35pp.,eprintmath.NT/0406476
  • Philippon, P., Sombra, M., Géométrie Diophantienne et variétés toriques (2005) C. R. Math. Acad. Sci. Paris, 340, pp. 507-512
  • Philippon, P., Sombra, M., (2006) A Refinement of the Kušnirenko-Bernštein Estimate, , Manuscript arXiv:0709.3306
  • Rojas, J.M., Solving degenerate sparse polynomial systems faster (1999) J. Symbolic Comput., 28, pp. 155-186. , 1/2
  • Rojas, J.M., Denef, J., Algebraic geometry over four rings and the frontier of tractability (2000) Proceedings of A Conference on Hilbert's Tenth Problem and Related Subjects University of Gent 1-5 November 1999 Contemp. Math., 270, pp. 275-321. , AMS Providence
  • Rojas, J.M., Why polyhedra matter in non-linear equation solving (2003) Proceedings of the Conference on Algebraic Geometry and Geometric Modelling Vilnius, Lithuania 29 July-2 August 2002 Contemp. Math., 334, pp. 293-320. , AMS Providence
  • Rojas, J.M., Wang, X., Counting affine roots of polynomial systems via pointed Newton polytopes (1996) J. Complex., 12, pp. 116-133. , 2
  • Sabia, J., Solernó, P., Bounds for traces in complete intersections and degrees in the Nullstellensatz (1996) Appl. Algebra Eng. Commun. Comput., 6, pp. 353-376. , 6
  • Savage, J.E., (1998) Models of Computation. Exploring the Power of Computing, , Addison-Wesley Reading
  • Schost, E., Computing parametric geometric resolutions (2003) Appl. Algebra Eng. Commun. Comput., 13, pp. 349-393
  • Sommese, A., Wampler, C., (2005) The Numerical Solution of Systems of Polynomials Arising in Engineering and Science, , World Scientific Singapore
  • Storjohann, A., (2000) Algorithms for Matrix Canonical Forms, , Ph.D. thesis, ETH, Zürich, Switzerland
  • Strassen, V., Van Leeuwen, J., Algebraic complexity theory (1990) Handbook of Theoretical Computer Science, pp. 634-671. , Elsevier Amsterdam
  • Verschelde, J., Gatermann, K., Cools, R., Mixed volume computation by dynamic lifting applied to polynomial system solving (1996) Discrete Comput. Geom., 16, pp. 69-112. , 1
  • Verschelde, J., Verlinden, P., Cools, R., Homotopies exploiting Newton polytopes for solving sparse polynomial systems (1994) SIAM J. Numer. Anal., 31, pp. 915-930. , 3
  • Von Zur Gathen, J., Gruska, J., Rovan, B., Wiedermann, J., Parallel arithmetic computations: A survey (1986) Proceedings of the 12th International Symposium on Mathematical Foundations of Computer Science Bratislava, Czechoslovakia 25-29 August 1986 Lecture Notes in Comput. Sci., 233, pp. 93-112. , Springer Berlin
  • Von Zur Gathen, J., Gerhard, J., (1999) Modern Computer Algebra, , Cambridge University Press Cambridge
  • Walker, R.J., (1950) Algebraic Curves, , Dover New York
  • Zippel, R., (1993) Effective Polynomial Computation Kluwer Int. Ser. Eng. Comput. Sci., 241. , Kluwer Dordrecht

Citas:

---------- APA ----------
Jeronimo, G., Matera, G., Solernó, P. & Waissbein, A. (2009) . Deformation techniques for sparse systems. Foundations of Computational Mathematics, 9(1), 1-50.
http://dx.doi.org/10.1007/s10208-008-9024-2
---------- CHICAGO ----------
Jeronimo, G., Matera, G., Solernó, P., Waissbein, A. "Deformation techniques for sparse systems" . Foundations of Computational Mathematics 9, no. 1 (2009) : 1-50.
http://dx.doi.org/10.1007/s10208-008-9024-2
---------- MLA ----------
Jeronimo, G., Matera, G., Solernó, P., Waissbein, A. "Deformation techniques for sparse systems" . Foundations of Computational Mathematics, vol. 9, no. 1, 2009, pp. 1-50.
http://dx.doi.org/10.1007/s10208-008-9024-2
---------- VANCOUVER ----------
Jeronimo, G., Matera, G., Solernó, P., Waissbein, A. Deformation techniques for sparse systems. Found. Comput. Math. 2009;9(1):1-50.
http://dx.doi.org/10.1007/s10208-008-9024-2