Canonical comprehensive Gröbner bases

ABSTRACT

Comprehensive Gröbner bases for parametric polynomial ideals were introduced, constructed, and studied by the author in 1992. Since then the construction has been implemented in the computer algebra systems ALDES/SAC-2, MAS, REDUCE and MAPLE. A comprehensive Gröbner basis is a finite subset G of a parametric polynomial ideal I such that σ(G) constitutes a Gröbner basis of the ideal generated by σ(I) under all specializations σ of the parameters in arbitrary fields. This concept has found numerous applications. In contrast to reduced Gröbner bases, however, no concept of a canonical comprehensive Gröbner basis was known that depends only on the ideal and the term order. In this note we find such a concept under very general assumptions on the parameter ring. After proving the existence and essential uniqueness of canonical comprehensive Gröbner bases in a non-constructive way, we provide a corresponding construction for the classical case, where the parameter ring is a multivariate polynomial ring. It proceeds via the construction of a canonical faithful Gröbner system. Some simple examples illustrate the features of canonical comprehensive Gröbner bases. Besides their theoretical importance, canonical comprehensive Gröbner bases are also of potential interest for efficiency reasons as indicated by the research of A. Montes.

REFERENCES

• 1: T. Becker. Gröbner bases versus d-Gröbner bases, and Gröbner bases under specialization. AAECC, 5:1-8, 1994.
• 2: Thomas Becker , Volker Weispfenning, The Chinese remainder problem, multivariate interpolation, and Gröbner bases, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.64-69, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120703]
• 3: Thomas Becker , Volker Weispfenning , Heinz Kredel, Gro¨bner bases: a computational approach to commutative algebra, Springer-Verlag, London, 1993
• 4: D. Eisenbud, C. Huneke, and W. Vasconcelos. Direct methods for primary decomposition. Invent. Math., 110:207-235, 1992.
• 5: W. Faas. Konstruktion umfassender Gröbner Basen in SCRATCHPAD II. Diploma thesis, Universität Passau, März 1992.
• 6: E. Fortuna, P. Gianni, and B. Trager. Degree reduction under specialization. J. pure and applied algebra, 164(1-2):153-164, 2001. Proceedings MEGA 2000.
• 7: Michael Kalkbrener, On the stability of Groübner bases under specializations, Journal of Symbolic Computation, v.24 n.1, p.51-58, July 1997 [doi>10.1006/jsco.1997.0113]
• 8: H. Kredel and V. Weispfenning. Parametric Gröbner bases in rings of solvable type. In Proceedings: IV. Intern. Conference on Computer Algebra in Physical Research (Joint Institute for Nuclear Research Dubna, USSR, May 1990), pages 236-244, Singapore, 1991. World Scientific.
• 9: Antonio Montes , Jordi Castro, Solving the load flow problem using Gro¨bner basis, ACM SIGSAM Bulletin, v.29 n.1, p.1-13, Jan. 1995 [doi>10.1145/216685.216686]
• 10: Antonio Montes, Algebraic solution of the load-flow problem for a 4-nodes electrical network, Mathematics and Computers in Simulation, v.45 n.1-2, p.163-174, Jan. 31, 1998
• 11: A. Montes. Basic algorithm for specialization in Gröbner bases. In I. Bermejo, editor, Actas de EACA-99, pages 215-228, Tenerife, 1999. Universidad de La Laguna.
• 12: Antonio Montes, A new algorithm for discussing Gröbner bases with parameters, Journal of Symbolic Computation, v.33 n.2, p.183-208, February 2002 [doi>10.1006/jsco.2001.0504]
• 13: M. Pesch. Computing Comprehensive Gröbner Bases using MAS. User Manual, Sept. 1994.
• 14: A. Pethö, J. Stein, T. Weis, and H. G. Zimmer. Computing the torsion group of elliptic curves by the method of Gröbner bases. In M. Bronstein, J. Grabmeier, and V. Weispfenning, editors, Symbolic Rewriting Techniques, volume 15 of Progress in Computer Science and Applied Logic, pages 245-265. Birkhäuser Verlag, 1998.
• 15: Marie-Françoise Roy, Aspect graphs of algebraic surfaces, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.135-143, July 06-08, 1993, Kiev, Ukraine [doi>10.1145/164081.164106]
• 16: M.-F. Roy and T. v. Effelterre. Aspect graphs of algebraic surfaces. Technical report, IRMAR, University of Rennes, 1995. available at URL: http://www.riaca.win.tue.nl/CAN/Research_Areas/AI/Vision/Aspect_graphs/Kiev_Last/Kiev_Last.html.
• 17: E. Schönfeld. Parametrische Gröbnerbasen im Computeralgebrasystem ALDES/SAC-2. Diploma thesis, Universität Passau, D-94030 Passau, Germany, May 1991.
• 18: Volker Weispfenning, Comprehensive Gro¨bner bases, Journal of Symbolic Computation, v.14 n.1, p.1-29, July 1992 [doi>10.1016/0747-7171(92)90023-W]
• 19: V. Weispfenning. Solving parametric polynomial equations and inequalities by symbolic algorithms. In Proceeding of the workshop: "Computer Algebra in Science and Engineering", Bielefeld, Aug'94, pages 163-179, Singapore, 1995. World Scientific.
• 20: O. Zariski and P. Samuel. Commutative Algebra I, II. Van Nostrand Reinhold Company, New York, 1958.

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:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Linear approximation

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Standardization