On implementing Buchberger's algorithm for Grobner bases

ABSTRACT

An implementation in the Maple system of Buchberger's algorithm for computing Gröbner bases is described. The efficiency of the algorithm is significantly affected by choices of polynomial representations, by the use of criteria, and by the type of coefficient arithmetic used for polynomial reductions. The improvement possible through a slightly modified application of the criteria is demonstrated by presenting time and space statistics for some sample problems. A fraction-free method for polynomial reduction is presented. Timings on problems with integer and polynomial coefficients show that a fraction-free approach is recommended.

REFERENCES

• 1: W. BSge, R. Gebauer, H. Kredel: "Some Examples for Solving Systems of Algebraic Equations by Calculating GrSbner B~ses", J. Symbolic Computation, Vol. 1, 1985 (to appear).
• 2: B. Buchberger, A theoretical basis for the reduction of polynomials to canonical forms, ACM SIGSAM Bulletin, v.10 n.3, p.19-29, August 1976 [doi>10.1145/1088216.1088219]
• 3: B. Buchberger, Some properties of Gröbner-bases for polynomial ideals, ACM SIGSAM Bulletin, v.10 n.4, p.19-24, November 1976 [doi>10.1145/1088222.1088224]
• 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: B. Buehberger: "GrSbner Bases" An Algorlthmlc Method in Polynomial Ideal Theory", in Progress, directions and open problem8 in multidimensional systems theory, (N.K. Bose, ed.), D. Reidel Publishing Co., 1985, pp.184-232.
• 6: B. Buehberger, F. Winkler: '*Miscellaneous Results on the construction of Gr~bner bases for polynomial ideals", Teeh. Rep. 137, Univ. of Linz, Math. Inst., 1979.
• 7: J.C. Butcher: "Stability }Properties for a General Cla~s of Methods for Ordinary Differential Equations", SIAM J. Numer. Anal. 18, No. 1, 1981, pp.37-44.
• 8: J.C. Butcher: "An application of the Runge Kutta space", BIT Computer Science Numer. Math., Vol. 24, 1984, pp.425-440.
• 9: Bruce W. Char , Keith O. Geddes , Gaston H. Gonnet, GCDHEU: Heuristic Polynomial GCD Algorithm Based on Integer GCD Computation, Proceedings of the International Symposium on Symbolic and Algebraic Computation, p.285-296, July 09-11, 1984
• 10: Bruce W. Char , Keith O. Geddes , W. Morven Gentleman , Gaston H. Gonnet, The design of maple: A compact, portable and powerful computer algebra system, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.101-115, March 28-30, 1983
• 11: B.W. Char, K.O. Geddes, G.H. Gonnet, S.M. Watt: ~Iaple User s Guide , WATCOM Publications, Waterloo, Ontario, 1985.
• 12: G. Fee (Private communication.)
• 13: Anthony C. Hearn, Non-modular computation of polynomial GCD's using trial division, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.227-239, June 01, 1979
• 14: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 15: R. Loos: "Generalized polynomial remainder sequences", in Computer Algebra- Symbolic and Algebraic Computation, (B. Buehberger, R. Loos and G.E. Collins, ed.), Springer, Wien New York, 2nd edition, 1983, pp.115-138.
• 16: M.B. Monagan (Private communication.)
• 17: Michael E. Pohst , David Y. Y. Yun, On solving systems of algebraic equations via ideal bases and elimination theory, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.206-211, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806397]
• 18: Ken Rimey, Problem section (rotating fluids): a system of polynomial equations and a solution by an unusual method, ACM SIGSAM Bulletin, v.18 n.1, p.30-32, February 1984 [doi>10.1145/1089348.1089353]
• 19: W. Trinks: '~L~ber B. Buchbergers Verfahren, Systeme algebraischer Gleichungen zu losen", J. Number Theory, Vol. 10, No. 4, Nov. 1978, pp.475-488.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems

          Nouns: Maple

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms, Theory