Degree bounds and lifting techniques for triangular sets

ABSTRACT

We study the representation of the solutions of a polynomial system by triangular sets, and concentrate on the positive-dimensional case. We reduce to dimension zero by placing the free variables in the base-field, so the solutions can be represented by triangular sets with coefficients in a rational function field. First, we give bounds on the degree of these coefficients; then we show how to apply lifting techniques in this context, and point out the role played by the evaluation properties of the input system. Our algorithms are implemented in Magma; we present two applications.

REFERENCES

• 1: http://www.maths.usyd.edu.au:8000/u/magma/.
• 2: http://www.medicis.polytechnique.fr/.
• 3: P. Aubry. Ensembles triangulaires de polynômes et résolution de systèmes algébriques. Implantation en Axiom. PhD thesis, Université Paris VI, 1999.
• 4: Philippe Aubry , Daniel Lazard , Marc Moreno Maza, On the theories of triangular sets, Journal of Symbolic Computation, v.28 n.1-2, p.105-124, July/Aug. 1999 [doi>10.1006/jsco.1999.0269]
• 5: F. Boulier , D. Lazard , F. Ollivier , M. Petitot, Representation for the radical of a finitely generated differential ideal, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.158-166, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220367]
• 6: S. Dellière. Triangularisation de systèmes constructibles -- Application à l'évaluation dynamique. PhD thesis, Université de Limoges, 1999.
• 7: G. Gallo and B. Mishra. Efficient algorithms and bounds for Wu-Ritt characteristic sets. In Proceedings MEGA '90. Birkhäuser, 1990.
• 8: P. Gaudry. Algorithmique des courbes hyperelliptiques et applications à la cryptologie. PhD thesis, École polytechnique, 2000.
• 9: Pierrick Gaudry , Éric Schost, On the Invariants of the Quotients of the Jacobian of a Curve of Genus 2, Proceedings of the 14th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.373-386, November 26-30, 2001
• 10: M. Giusti, K. Hägele, J. Heintz, J. E. Morais, J. L. Montaña, and L. M. Pardo. Lower bounds for Diophantine approximation. Number 117,118 in J. of Pure and App. Algebra, pages 277-317, 1997.
• 11: M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo. Straight-line programs in geometric elimination theory. J. of Pure and App. Algebra, 124:101-146, 1998.
• 12: Marc Giusti , Joos Heintz , Jose Enrique Morais , Luis M. Pardo, When Polynomial Equation Systems Can Be "Solved" Fast?, Proceedings of the 11th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.205-231, July 17-22, 1995
• 13: Marc Giusti , Grégoire Lecerf , Bruno Salvy, A Gröbner free alternative for polynomial system solving, Journal of Complexity, v.17 n.1, p.154-211, March 1, 2001 [doi>10.1006/jcom.2000.0571]
• 14: J. Heintz. Definability and fast quantifier elimination in algebraically closed fields. Theor. Comput. Sci., 24(3):239-277, 1983.
• 15: Joos Heintz , Teresa Krick , Susana Puddu , Juan Sabia , Ariel Waissbein, Deformation techniques for efficient polynomial equation solving, Journal of Complexity, v.16 n.1, p.70-109, March 2000 [doi>10.1006/jcom.1999.0529]
• 16: M. Kalkbrener. Three contributions to elimination theory. PhD thesis, Kepler University, Linz, 1991.
• 17: T. Krick, J. Sabia, and P. Solernó. On intrinsic bounds in the Nullstellensatz. AAECC Journal, 8:125-134, 1997.
• 18: D. Lazard, Solving zero-dimensional algebraic systems, Journal of Symbolic Computation, v.13 n.2, p.117-131, Feb. 1992 [doi>10.1016/S0747-7171(08)80086-7]
• 19: M. Moreno Maza. Calculs de pgcd au-dessus des tours d'extensions simples et résolution des systèmes d'équations algébriques. PhD thesis, Université Paris VI, 1997.
• 20: Sally Morrison, The differential ideal [P]: M^∞ , Journal of Symbolic Computation, v.28 n.4-5, p.631-656, Oct./Nov. 1999 [doi>10.1006/jsco.1999.0318]
• 21: J. Sabia and P. Solernó. Bounds for traces in complete intersections and degrees in the Nullstellensatz. AAECC Journal, 6:353-376, 1996.
• 22: É. Schost. Computing parametric geometric resolutions. Preprint École polytechnique, 2000.
• 23: É. Schost. Sur la résolution des systèmes polynomiaux à paramètres. PhD thesis, École polytechnique, 2000.
• 24: Agnes Szanto , Dexter Kozen, Computation with polynomial systems, 1999
• 25: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Standards

General Terms:
Algorithms, Documentation, Experimentation