A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)

ABSTRACT

This paper introduces a new efficient algorithm for computing Gröbner bases. We replace the Buchberger criteria by an optimal criteria. We give a proof that the resulting algorithm (called F5) generates no useless critical pairs if the input is a regular sequence. This a new result by itself but a first implementation of the algorithm F5 shows that it is also very efficient in practice: for instance previously untractable problems can be solved (cyclic 10). In practice for most examples there is no reduction to zero. We illustrate this algorithm by one detailed example.

REFERENCES

• 1: ADAMS, W., AND LOUSTAUNAU, P. An introduction to Gröbner Bases, vol. 3 of Graduate Studies in Mathematics. American Mathematical Society, 1994.
• 2: Thomas Becker , Volker Weispfenning , Heinz Kredel, Gro¨bner bases: a computational approach to commutative algebra, Springer-Verlag, London, 1993
• 3: BUCHBERGER B. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, Innsbruck, 1965.
• 4: Bruno Buchberger, A criterion for detecting unnecessary reductions in the construction of Groebner bases, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.3-21, June 01, 1979
• 5: BUCHBERGER B. Gröbner Bases : an Algorithmic Method in Polynomial Ideal Theory. In Recent trends in multidimensional system theory, Ed. Bose, 1985.
• 6: FAUGÈRE J. C. A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra 139, 1-3 (June 1999), 61-88.
• 7: Rüdiger Gebauer , H. Michael Möller, Buchberger's algorithm and staggered linear bases, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.218-221, July 21-23, 1986, Waterloo, Ontario, Canada [doi>10.1145/32439.32482]
• 8: GREUEL G.-M. AND PFISTER G. AND SCHOENEMANN H. SINGULAR 2.0, July 2002. http://www.singular.uni-kl.de/.
• 9: Daniel Lazard, Gröbner-Bases, Gaussian elimination and resolution of systems of algebraic equations, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.146-156, March 28-30, 1983
• 10: H. Michael Möller , Teo Mora , Carlo Traverso, Gröbner bases computation using syzygies, Papers from the international symposium on Symbolic and algebraic computation, p.320-328, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143343]
• 11: Vladimir P. Gerdt , Yuri A. Blinkov, Involutive bases of polynomial ideals, Mathematics and Computers in Simulation, v.45 n.5-6, p.519-541, March 1998 [doi>10.1016/S0378-4754(97)00127-4]

INDEX TERMS

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

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

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

General Terms:
Algorithms, Design, Theory