Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Suppose we are given a parametric polynomial equation system encoded by an arithmetic circuit, which represents a generically flat and unramified family of zero-dimensional algebraic varieties. Let us also assume that there is given the complete description of the solution of a particular unramified parameter instance of our system. We show that it is possible to "move" the given particular solution along the parameter space in order to reconstruct - by means of an arithmetic circuit - the coordinates of the solutions of the system for an arbitrary parameter instance. The underlying algorithm is highly efficient, i.e., polynomial in the syntactic description of the input and the following geometric invariants: the number of solutions of a typical parameter instance and the degree of the polynomials occurring in the output. In fact, we prove a slightly more general result, which implies the previous statement by means of a well-known primitive element algorithm. We produce an efficient algorithmic description of the hypersurface obtained projecting polynomially the given generically flat family of varieties into a suitable affine space. © 2000 Academic Press.

Registro:

Documento: Artículo
Título:Deformation Techniques for Efficient Polynomial Equation Solving
Autor:Heintz, J.; Krick, T.; Puddu, S.; Sabia, J.; Waissbein, A.
Filiación:Departamento de Matemática, Fac. de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pab. I, 1428, Buenos Aires, Argentina
Departamento de Matemática, Estadística y Comp., Universidad de Cantabria, Avda. de los Castros s/n, E-39071, Santander, Spain
Palabras clave:Polynomial equation system; arithmetic circuit; shape (or primitive element) lemma; Newton-Hensel iteration
Año:2000
Volumen:16
Número:1
Página de inicio:70
Página de fin:109
DOI: http://dx.doi.org/10.1006/jcom.1999.0529
Título revista:Journal of Complexity
Título revista abreviado:J. Complexity
ISSN:0885064X
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0885064X_v16_n1_p70_Heintz.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v16_n1_p70_Heintz

Referencias:

  • Auzinger, W., Stetter, H.J., An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations (1988) International Series of Numerical Mathematics, , Basel: Birkhäuser. p. 11-30
  • Bürgisser, P., Clausen, M., Amin Shokrollahi, M., Algebraic Complexity Theory (1997) Grundlehren der Mathematischen Wissenschaften, 315. , New York/Berlin: Springer-Verlag
  • Bass, H., Connelle, E., Wright, T., The Jacobian conjecture: Reduction of degree and formal expansion of the inverse (1982) Bull. Amer. Math. Soc., 7, pp. 287-330
  • Berkowitz, S.J., On computing the determinant in small parallel time using a small number of processors (1984) Inform. Process. Lett., 18, pp. 147-150
  • Bank, B., Giusti, M., Heintz, J., Mbakop, G., Polar varieties and efficient real equation solving: The hypersurface case (1997) J. Complexity, 13, pp. 5-27
  • Borodin, A., Time space tradeoffs (getting closer to the barrier?) (1993) Algorithms and Computation, Proceedings 4, ISSAC Lecture Notes in Comput. Sci., 762. , New York/Berlin: Springer-Verlag. p. 209-220
  • Basu, S., Pollack, R., Roy, M.-F., On computing a set of points meeting every cell defined by a family of polynomials on a variety (1997) J. Complexity, 13, pp. 28-37
  • Bruno, N., (1998) Esquemas de Compilación de Circuitos Aritméticos Uniformes Descriptos Por Medio de Funciones Generatrices, , Universidad de CórdobaFaMAF
  • Buchberger, B., Gröbner bases: An algorithmic method in polynomial ideal theory (1985) Multidimensional System Theory, pp. 374-383. , N. K. Bose. Dordrecht: Reidel
  • Canny, J., Generalised characteristic polynomials (1990) J. Symbolic Comput., 9, pp. 241-250
  • Castro, D., (1997) Sobre la Complejidad de la Aproximación Diofántica Y Los Fundamentos del Análisis Numérico, , Santander: Universidad de Cantabria
  • 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
  • Colin, A., (1997) Théorie des Invariants Effective, , Palaiseau-Paris: Ecole Polytechnique
  • Fulton, W., Intersection Theory (1984) Ergebnisse der Mathematik, , New York/Berlin: Springer-Verlag
  • 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) Computational Algebraic Geometry and Commutative Algebra, Symposia Mathematica, pp. 216-256. , D. Eisenbud, & L. Robbiano. Cambridge: Cambridge Univ. Press
  • 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., Hägele, K., Lecerf, G., Marchand, J., Salvy, B., (1997) Research Report
  • 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., Le rôle des structures de données dans les problèmes d'élimination (1997) C. R. Acad. Sci. Paris, 325, pp. 1223-1228
  • Gianni, P., Mora, T., Algebraic solution of systems of polynomial equations using Gröbner bases (1989) Proceedings AAECC-5 Lecture Notes in Comput. Sci., 356. , New York/Berlin: Springer-Verlag. p. 247-257
  • Grigoriev, D.yu., Vorobjov N.N., Jr., Solving systems of polynomial inequalities in sub-exponential time (1988) J. Symbolic Comput., 5, pp. 37-64
  • Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. Comput. Sci., 24, pp. 239-277
  • Hägele, K., Morais, J.E., Pardo, L.M., Sombra, M., J. Pure Appl. Algebra, , On the intrinsic complexity of the arithmetic Nullstellensatz in press
  • Heintz, J., Roy, M.-F., Solernó, P., Sur la complexité du principe de Tarski-Seidenberg (1990) Bull. Soc. Math. France, 118, pp. 101-126
  • Iversen, B., Generic local structure of the morphisms in commutative algebra (1973) Lecture Notes in Math., , New York/Berlin: Springer-Verlag
  • Kaltofen, E., Computing with polynomials given by straight-line programs. I. Greatest common divisors (1985) Proceedings of the 17th Ann. ACM Symposium on Theory of Computing, Providence, RI, , New York: ACM Press. p. 131-142
  • Koenig, J., (1903) Einleitung in Die Allgemeine Theorie der Algebraischen Grössen, , Leipzig: Teubner
  • Kovacs, P., Minimum degree solutions for the inverse kinematics problem by application of the Buchberger algorithm (1990) Proceedings of the 2nd Int. Workshop on Advances in Robot Kinematics, University of Linz, Austria, September 10-12, 1990, , New York/Berlin: Springer-Verlag
  • 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. Algorithms in Algebraic Geometry and Applications, Proceedings of MEGA'94. Basel: Birkhäuser Verlag
  • Kronecker, L., Grundzüge einer arithmetischen Theorie de algebraischen Grössen (1882) J. Reine Angew. Math., 92, pp. 1-22
  • Gonzalez Lopez, M.J., Gonzalez Vega, L., Newton identities in the multivariate case: Pham systems (1998) London Mathematical Society Lecture Notes Series, , Cambridge: Cambridge Univ. Press. p. 351-366
  • Macaulay, F.S., (1916) Algebraic Theory of Module Systems, , Cambridge: Cambridge Univ. Press
  • Matera, G., (1997) Sobre la Complejidad en Espacio Y Tiempo de la Eliminación Geométrica, , Universidad de Buenos Aires
  • Mishra, B., (1993) Algorithmic Algebra, , New York: Springer-Verlag
  • Morais, J.E., (1997) Resolución Eficaz de Sistemas de Ecuaciones Polinomiales, , Santander: Universidad de Cantabria
  • Mourrain, B., Pan, V., Solving special polynomial systems by using structural matrices and algebraic residues (1997) Proceedings Foundations of Computational Mathematics, FOCM'97, pp. 287-304. , F. Cucker, & M. Shub. New York/Berlin: Springer-Verlag
  • Narasimhan, R., Introduction to the theory of analytic spaces (1966) Lecture Notes in Math., , New York/Berlin: Springer-Verlag
  • Renegar, J., On the computational complexity and geometry of the first-order theory of the reals. Part I. Introduction, preliminaries, the geometry of semi-algebraic sets, the decision problem for the existential theory of the reals (1992) J. Symbolic Comput., 13, pp. 255-299
  • Schmid, J., On the affine Bézout inequality (1995) Manuscripta Math., 88, pp. 225-232
  • Schönhage, A., Grotefeld, F.W., Vetter, E., (1994) Fast Algorithms: A Multitape Turing Machine Implementation, , Mannheim: Wissenschaftsverlag
  • Sombra, M., Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz (1997) J. Pure Appl. Algebra, 117-118, pp. 565-599
  • Shub, M., Smale, S., Complexity of Bézout's theorem. I. Geometric aspects (1993) J. Amer. Math. Soc., 6, pp. 459-501
  • Shub, M., Smale, S., Complexity of Bézout's theorem. II. Volumes and probabilities (1993) Proceedings of MEGA'92 Progress in Mathematics, 109. , Basel: Birkhäuser Verlag. p. 267-285
  • Shub, M., Smale, S., Complexity of Bézout's theorem. III. Condition number and packing (1993) J. Complexity, 9, pp. 4-14
  • Shub, M., Smale, S., Complexity of Bézout's theorem. V. Polynomial time (1994) Theoret. Comput. Sci., 133, pp. 141-164
  • Sabia, J., Solernó, P., Bounds for traces in complete intersections and degrees in the Nullstellensatz (1996) Appl. Algebra Engrg. Comm. Comput., 6, pp. 353-376
  • Shub, M., Smale, S., Complexity of Bezout's theorem. IV. Probability of success and extensions (1996) SIAM J. Numer. Anal., 33, pp. 128-148
  • Strassen, V., Vermeidung von Divisionen (1973) J. Reine Angew. Math., 264, pp. 182-202
  • (1997) Some Remarks on the Time-space Tradeoff of Geometric Elimination Procedures, , TERA Development Group manuscript
  • Vallibouze, A., Computations of the Galois groups of the resolvent factors for the direct and indirect Galois problem (1995) Proceedings of AAECC-11, 948, pp. 456-468. , M. Giusti, G. Cohen, & T. Mora. Lecture Notes in Comput. Sci. New York/Berlin: Springer-Verlag
  • Verschelde, J., Haegemans, A., Homotopies for solving polynomial systems within a bounded domain (1994) Theoret. Comput. Sci., 133, pp. 165-185
  • Vogel, W., (1984) Results on Bezout's Theorem, , New York/Berlin: Springer-VerlagTata Institute of Fundamental Research
  • Von Zur Gathen, J., Parallel arithmetic computations: A survey (1986) Proceedings of the 12th Symposium on Mathematical Foundations of Computer Science, 233, pp. 93-112. , B. Rovan, J. Gruska, & J. Wiedermann. Lecture Notes in Comput. Sci. New York/Berlin: Springer-Verlag
  • Von Zur Gathen, J., Parallel linear algebra (1993) Synthesis of Parallel Algorithms, pp. 573-617. , J. H. Reif. CA: San Mateo
  • Weispfenning, V., Becker, T., Groebner Bases: A Computational Approach to Commutative Algebra (1993) Graduate Texts in Mathematics, 141. , New York/Berlin: Springer-Verlag
  • Zariski, O., Algebraic Surfaces (1995) Classics in Mathematics, , New York/Berlin: Springer-Verlag

Citas:

---------- APA ----------
Heintz, J., Krick, T., Puddu, S., Sabia, J. & Waissbein, A. (2000) . Deformation Techniques for Efficient Polynomial Equation Solving. Journal of Complexity, 16(1), 70-109.
http://dx.doi.org/10.1006/jcom.1999.0529
---------- CHICAGO ----------
Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A. "Deformation Techniques for Efficient Polynomial Equation Solving" . Journal of Complexity 16, no. 1 (2000) : 70-109.
http://dx.doi.org/10.1006/jcom.1999.0529
---------- MLA ----------
Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A. "Deformation Techniques for Efficient Polynomial Equation Solving" . Journal of Complexity, vol. 16, no. 1, 2000, pp. 70-109.
http://dx.doi.org/10.1006/jcom.1999.0529
---------- VANCOUVER ----------
Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A. Deformation Techniques for Efficient Polynomial Equation Solving. J. Complexity. 2000;16(1):70-109.
http://dx.doi.org/10.1006/jcom.1999.0529