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:

Let be given a parametric polynomial equation system which represents a generically unramified family of zero-dimensional algebraic varieties. We exhibit an efficient algorithm which computes a complete description of the solution set of an arbitrary parameter instance from a complete description of the infinitesimal structure of a particular ramified parameter instance of our family. This generalizes in the case of space curves previous methods of Heintz et al. and Schost, which require the given parameter instance to be unramified. We illustrate our method solving particular polynomial equation systems by deformation techniques. © 2004 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Polynomial equation solving by lifting procedures for ramified fibers
Autor:Bompadre, A.; Matera, G.; Wachenchauzer, R.; Waissbein, A.
Filiación:Departamento de Matemáticas, Facultad de Ciencias y Naturales, Ciudad Universitaria, Pabellón I (1428), Buenos Aires, Argentina
Instituto de Desarrollo Humano, Univ. Nacional de General Sarmiento, Campus Universitario, Jose M. Gutierrez 1150 (1613), Pcia. de Buenos Aires, Argentina
CONICET, Argentina
Departamento de Computación, Facultad de Ingeniería, Universidad de Buenos Aires, Av. Paseo Colón 850 (1063), Buenos Aires, Argentina
MIT Operations Research Center, Building E40-130, 77, Massachusetts Avenue, Cambridge, MA 02139, United States
Palabras clave:Efficient polynomial equation solving; Newton-Hensel lifting; Puiseux expansions of space curves; Ramified fibers of dominant mappings; Algebra; Algorithms; Iterative methods; Parameter estimation; Problem solving; Theorem proving; Vectors; Efficient polynomial equation solving; Newton-Hensel lifting; Puiseux expansions of space curves; Ramified fibers of dominant mappings; Polynomials
Año:2004
Volumen:315
Número:2-3
Página de inicio:335
Página de fin:369
DOI: http://dx.doi.org/10.1016/j.tcs.2004.01.015
Título revista:Theoretical Computer Science
Título revista abreviado:Theor Comput Sci
ISSN:03043975
CODEN:TCSCD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v315_n2-3_p335_Bompadre

Referencias:

  • Allgower, E., Georg, K., Numerical Continuation Methods: An Introduction (1990) Springer Series in Computational Mathematics, 13. , Springer, Heidelberg
  • Alonso, M., Becker, E., Roy, M.-F., Wörmann, T., Zeroes, multiplicities and idempotents for zerodimensional systems (1996) Algorithms in Algebraic Geometry and Applications Progress in Mathematics, 143, pp. 1-15. , L. González-Vega, T. Recio (Eds.), Birkhäuser, Basel
  • Alonso, M., Niesi, G., Mora, T., Raimondo, M., Local parametrizations of space curves at singular points (1991) Springer Eurographic Seminar Series, pp. 61-90. , I. Herman, C. Pienovi (Eds.), Computer Graphics and Mathematics, Springer, Berlin Heidelberg, New York
  • Alonso, M., Niesi, G., Mora, T., Raimondo, M., An algorithm for computing analytic branches of space curves at singular points (1992) Proc. 1992 International Workshop on Mathematical Mechanization, pp. 135-166. , W.-T. Wu, M.-D. Cheng (Eds.), Int. Academic Pub
  • Artin, M., Lectures on deformation of singularities (1976) Tata Inst. Fund. Res.
  • Bayer, D., Mumford, D., What can be computed in algebraic geometry? (1993) Computational Algebraic Geometry and Commutative Algebra, Symp. Mathematics, 34, pp. 1-49. , D. Eisenbud, L. Robbiano (Eds.), Cambridge University Press, Cambridge
  • Becker, T., Weispfenning, V., Gröbner bases, A Computational Approach to Commutative Algebra (1993) Springer Graduate Texts in Mathematics, 141. , Springer, Berlin, Heidelberg, New York
  • Bini, D., Mourrain, B., Polynomial Test Suite, , http://www-sop.inria.fr/saga
  • Bini, D., Pan, V., (1994) Polynomial and Matrix Computations, , Basel: Birkhäuser
  • Blum, L., Cucker, F., Shub, M., Smale, S., (1998) Complexity and Real Computation, , New York, Berlin, Heidelberg: Springer
  • Bompadre, A., (2000) Un Problema de Eliminación Geométrica en Sistemas de Pham-brieskorn, , Master's Thesis, Fac. Cs. Exactas y Nat., Universidad de Buenos Aires
  • Bompadre, A., Matera, G., Wachenchauzer, R., Waissbein, A., Lifting procedures for ramified fibers and polynomial equation solving (2001) Proc. Workshop Argentino de Informática Teórica, WAIT'01, 30, pp. 13-31. , M. Frías, J. Heintz (Eds.), Buenos Aires, September 2001, Anales JAIIO, Buenos Aires
  • Bonder, J.F., Rossi, J., Blow-up vs. spurious steady solutions (2001) Proc. Amer. Math. Soc., 129 (1), pp. 139-144
  • Borodin, A., Time space tradeoffs (getting closer to the barriers?) (1993) Lecture Notes in Computer Science, 762, pp. 209-220. , 4th Internat. Symp. on Algorithms and Computation, ISAAC '93, Hong Kong, December 1993, Springer, Berlin
  • Bürgisser, P., Clausen, M., Shokrollahi, M., Algebraic Complexity Theory (1997) Grundlehren der Mathematischen Wissenschaften, 315. , Springer, Berlin, Heidelberg, New York
  • Castro, D., Giusti, M., Heintz, J., Matera, G., Pardo, L.M., The hardness of polynomial equation solving (2003) Found. Comput. Math., 3 (4), pp. 347-420
  • Chipot, M., Fila, M., Quittner, P., Stationary solutions, blow up and convergence to stationary solutions for semilinear parabolic equations with nonlinear boundary conditions (1991) Acta Math. Univ. Comenianae, 60 (1), pp. 35-103
  • Chistov, A., Grigoriev, D., (1983) Subexponential Time Solving Systems of Algebraic Equations I, II, , LOMI preprints E-9-83, E-10-83, Steklov Institute, Leningrad
  • Cox, D., Little, J., O'shea, D., (1992) Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Undergraduate Texts in Mathematics, , Berlin, Heidelberg, New York: Springer
  • Cox, D., Little, J., O'Shea, D., Using Algebraic Geometry (1998) Graduate Texts in Mathematics, 185. , Springer, Berlin, Heidelberg, New York
  • Cox, D., Sturmfels, B., Applications of computational algebraic geometry (1998) Proc. Symp. Applied Mathematics, 53. , AMS, Providence, RI
  • Danilov, V., Algebraic varieties and schemes (1994) Encyclopedia Mathematics Sciences, 23, pp. 167-297. , I. Shafarevich. Algebraic Geometry I. Berlin: Springer
  • Duval, D., Rational Puiseux expansions (1989) Compositio Math., 70, pp. 119-154
  • Eisenbud, D., Commutative Algebra with a View Toward Algebraic Geometry (1995) Graduate Texts in Mathematics, 150. , Springer, Berlin, Heidelberg, New York
  • Ferreira, R., Groisman, P., Rossi, J., Numerical blow-up for a nonlinear problem with a nonlinear boundary condition (2002) Math. Models Methods Appl. Sci., 12 (4), pp. 461-484
  • Fulton, W., (1984) Intersection Theory, , Springer, Berlin, Heidelberg, New York
  • Gianni, P., Mora, T., Algebraic solution of systems of polynomial equations using Gröbner bases (1987) Lecture Notes in Computer Science, 356, pp. 247-257. , L. Huguet, A. Poli (Eds.), Proc. AAECC-5, Menorca, Spain, June, Springer, Berlin
  • 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., La détermination des points isolés et de la dimension d'une variété algébrique peut se faire en temps polynomial (1993) Symposia Mathematica, 34, pp. 216-256. , D. Eisenbud, L. Robbiano (Eds.), Computational Algebraic Geometry and Commutative Algebra, Cambridge University Press, Cambridge, MA
  • 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., Heintz, J., Morais, J.E., Pardo, L.M., When polynomial equation systems can be solved fast? (1995) Lecture Notes in Computer Science, 948, pp. 205-231. , G. Cohen, M. Giusti, T. Mora (Eds.), Proc. AAECC-11, Springer, Berlin
  • Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M., Le rôle des structures de données dans les problèmes d'élimination (1997) C. R. Acad. Sci. Paris, 325, pp. 1223-1228
  • Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complexity, 17 (1), pp. 154-211
  • Gonzalez-Lopez, M., Gonzalez-Vega, L., Newton identities in the multivariate case: Pham systems (1998) London Math. SLNS, 251, pp. 351-366. , B. Buchberger et al. (Eds.), Gröbner Bases and Applications, Cambridge University Press, Cambridge, MA
  • Gonzalez-Vega, L., A special quantifier elimination algorithm for Pham systems (1998) Contemporary Mathematics, 253, pp. 115-366. , C. Detzell et al. Real algebraic geometry and ordered structures. Providence, RI: AMS
  • Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. Comput. Sci., 24 (3), pp. 239-277
  • Heintz, J., On the computational complexity of polynomials and bilinear mappings. A survey (1987) Lecture Notes in Computer Science, 356, pp. 269-300. , L. Huguet, A. Poli (Eds.), Proc. AAECC-5, Menorca, Spain, June, Springer, Berlin
  • Heintz, J., Jerónimo, G., Sabia, J., San Marti;́n, J., Solernó, P., On the multihomogeneous Bézout theorem (2002) Intersection Theory and Deformation Algorithms, , 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. Complexity, 16 (1), pp. 70-109
  • Heintz, J., Matera, G., Waissbein, A., On the time-space complexity of geometric elimination procedures (2001) Appl. Algebra Engrg. Comm. Comp., 11 (4), pp. 239-296
  • Henry, D., Geometric Theory of Semilinear Parabolic Equations (1981) Lecture Notes in Mathematics, 840. , Berlin, Heideilberg: Springer
  • Huber, B., Sturmfels, B., A polyhedral method for solving sparse polynomial systems (1995) Math. Comput., 64 (112), pp. 1541-1555
  • Krick, T., Pardo, L.M., A computational method for Diophantine approximation (1996) Progress in Mathematics, 143, pp. 193-254. , L. González-Vega, & T. Recio. Basel: Birkhäuser
  • Kronecker, L., Grundzüge einer arithmetischen Theorie der algebraischen Grössen (1882) J. Reine Angew. Math., 92, pp. 1-122
  • Kunz, E., (1985) Introduction to Commutative Algebra and Algebraic Geometry, , Boston: Birkhäuser
  • Lickteig, T., Roy, M.-F., Cauchy index computation (1997) Calcolo, 33, pp. 337-351
  • Macaulay, F.S., (1916) The Algebraic Theory of Modular Systems, , Cambridge: Cambridge University Press
  • Matsumura, H., (1986) Commutative Ring Theory, , Cambridge: Cambridge University Press
  • Mora, T., Pfister, G., Traverso, C., An introduction to the tangent cone algorithm (1992) Advances in Computing Research, 6, pp. 199-270. , C. Hoffmann (Ed.), Issues in robotics and non-linear geometry, JAI Press, Greenwich CT
  • Mourrain, B., Pan, V., Solving special polynomial systems by using structural matrices and algebraic residues (1997) Proc. FOCM'97, pp. 287-304. , F. Cucker, M. Shub (Eds.), Springer, Berlin, Heidelberg, New York
  • Mourrain, B., Pan, V., Multivariate polynomials, duality and structured matrices (2000) J. Complexity, 16 (1), pp. 110-180
  • Pardo, L.M., How lower and upper complexity bounds meet in elimination theory (1995) Lecture Notes in Computer Science, 948, pp. 33-69. , G. Cohen, M. Giusti, T. Mora (Eds.), Proc. AAECC-11, Springer, Berlin, Heidelberg, New York
  • Pardo, L.M., San Marti;́n, J., Deformation techniques to solve generalized Pham systems (2004) Theoret. Comput. Sci., , this Vol
  • Renegar, J., On the computational complexity and geometry of the first order theory of the reals I, II, III (1992) J. Symbolic Comput., 13 (3), pp. 255-352
  • Rheinboldt, W., Methods for solving systems of nonlinear equations (1998) CBMS-NSF Regional Conf. Series in Applied Mathematics, 70. , SIAM, Philadelphia
  • Rouillier, F., Solving zero-dimensional systems throught rational univariate representation (1997) Appl. Algebra Engrg. Comm. Comp., 9 (5), pp. 433-461
  • Savage, J., (1998) Models of Computation. Exploring the Power of Computing, , Reading, MA: Addison Wesley
  • Schost, E., Computing parametric geometric resolutions (2003) Appl. Algebra Engrg. Comm. Comp., 13, pp. 349-393
  • Schwartz, J., Fast probabilistic algorithms for verification of polynomial identities (1980) J. ACM, 27 (4), pp. 701-717
  • Shafarevich, I., (1994) Basic Algebraic Geometry: Varieties in Projective Space, , Berlin, Heidelberg, New York: Springer
  • Strassen, V., Algebraic complexity theory (1990) Handbook of Theoretical Computer Science, pp. 634-671. , van Leeuwen, J. (Ed.), Elsevier, Amsterdam, (Chapter 11)
  • Sturmfels, B., (2002) Solving Systems of Polynomial Equations, CBMS Regional Conference Series in Mathematics, , Providence, RI: AMS
  • Von zur Gathen, J., Parallel arithmetic computations: A survey (1986) Lecture Notes in Computer Science, 233, pp. 93-112. , B.R.J. Gruska, J. Wiedermann (Eds.), Proc. 12th Symp. MFCS, Bratislava, Czechoslovakia, 1986, Springer, Berlin
  • Walker, R., (1950) Algebraic Curves, , New York: Dover Publications Inc
  • Walsh, P., On the complexity of rational Puiseux expansions (1999) Pacific J. Math., 188 (2), pp. 369-387
  • Walsh, P., A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic, function (2000) Math. Comput., 69 (231), pp. 1167-1182
  • Zariski, O., (1995) Algebraic Surfaces, , Berlin, Heidelberg, New York: Springer
  • Zippel, R., Probabilistic algorithms for sparse polynomials (1979) Lecture Notes in Computer Science, 72, pp. 216-226. , Proc. EUROSAM'79, Marseille 1979, Springer, Berlin

Citas:

---------- APA ----------
Bompadre, A., Matera, G., Wachenchauzer, R. & Waissbein, A. (2004) . Polynomial equation solving by lifting procedures for ramified fibers. Theoretical Computer Science, 315(2-3), 335-369.
http://dx.doi.org/10.1016/j.tcs.2004.01.015
---------- CHICAGO ----------
Bompadre, A., Matera, G., Wachenchauzer, R., Waissbein, A. "Polynomial equation solving by lifting procedures for ramified fibers" . Theoretical Computer Science 315, no. 2-3 (2004) : 335-369.
http://dx.doi.org/10.1016/j.tcs.2004.01.015
---------- MLA ----------
Bompadre, A., Matera, G., Wachenchauzer, R., Waissbein, A. "Polynomial equation solving by lifting procedures for ramified fibers" . Theoretical Computer Science, vol. 315, no. 2-3, 2004, pp. 335-369.
http://dx.doi.org/10.1016/j.tcs.2004.01.015
---------- VANCOUVER ----------
Bompadre, A., Matera, G., Wachenchauzer, R., Waissbein, A. Polynomial equation solving by lifting procedures for ramified fibers. Theor Comput Sci. 2004;315(2-3):335-369.
http://dx.doi.org/10.1016/j.tcs.2004.01.015