Gröbner Bases Algorithm

The concept of Gröbner Bases was introduced by Bruno Buchberger in 1965 in the context of his work on performing algorithmic computations in residue classes of polynomial rings. Buchberger's algorithm for computing Gröbner Bases is a powerful tool for solving many important problems in polynomial ideal theory. The Algorithm was named after Wolfgang Gröbner who was the Ph.D. Advisor to Buchberger and who stimulated the research on the subject.

Polynomial Ideal Theory:
1. Canonical Simplification Problem Modulo Polynomial Ideals.
2. Decision Problems of Ideal Congruence and Membership.
3. The Problem of Computation in Residue Class Rings.
4. Polynomial Ideals over the Integers.
Systems of Equations:
1. The Problem of Exact Solution of Systems of Algebraic Equations.
2. Questions about the Solvability of Systems of Algebraic Equations.
3. Solution of Linear Homogeneous Equations with Polynomial Coefficients.
Non-Linear Computational Geometry:
1. Inverse Kinematics in Robot Programming.
2. Collision Detection for Superellepsoids.
3. Implicitization of Parametric Representations of Curves and Surfaces.
4. Inversion of Parametric Representations.
5. Detection of Singularities.
6. Automated Geometrical Theorem Proving.
7. Primary Decomposition of Implicitly defined geometrical objects.
Other Applications:
1. Decision whether a given polynomial ideal is principal.
2. Hilbert Functions of polynomial ideals.
3. Lasker-Noether Decomposition of polynomial ideals.
4. Free resolutions of polynomial ideals and syzygies.

Tutorial

This tutorial provides an introduction to the theory of Grobner Bases. It is based on the published literature on Grobner Bases. References that have been used to prepare this tutorial are listed in the Reference section of the tutorial. For a comprehensive list of references, the reader is refered to the next section. Now, please click to view the tutorial.

Implementations

Almost every Computer Algebra System contains some implementation of the Gröbner Bases Algorithm. None commercial packages implementations include:

GB: The purpose of the Faughre's GB package is to compute Gröbner basis of polynomials ideals, and to solve systems of algebraic equations. It is supposed to do quick computations, and has a quite poor documentation in English. The package is written in C and C++ by JC Faugere.

GRÖBNER: A library for computing Gröbner Bases based on SACLIB by W. Windsteiger and B. Buchberger. GRÖBNER is designed "polymorphically", i.e. in such a way that the implementation of algorithms for a domain is totally independent of the subdomains involved. The package is avialable via anonymous ftp.
Macaulay: A system for computation in algebraic geometry and commutative algebra by D. Bayer and M. Stillman.

Bibliography / GB

Attardi, G. - Traverso C.
A Strategy-Accurate Parallel Buchberger Algorithm
Proceedings of PASCO'94
World Scientific, 1994
Becker T. - Weispfenning V.
Grobner Bases: A Computational Approach to Commutative Algebra
Springer-Verlag, 1993.
Buchberger B.
An Algorithm for finding a basis for the residue class ring of a zero-dimensional polynomial ideal (in German)
Doctoral Dissertation
Math. Inst. University of Innsbruck, Austria, 1965.
Buchberger B.
A Theoretical Basis for the Reduction of Polynomials to Canonical Form
ACM SIGSAM Bulletin Vol. 10, No. 3
pp. 19-29, 1976.
Buchberger B.
Some Properties of Grobner Bases for Polynomial Ideals
ACM SIGSAM Bulletin Vol. 10, No. 4
pp. 19-24, 1976.
Buchberger B.
A Criterion for Detecting Unnecessary Reductions in the Construction of Grobner Basis
EUROSAM '79, Lecture Notes in Computer Science 72
Springer-Verlag
pp. 3-21, 1979.
Buchberger B.
A Note on the Complexity of Constructing Grobner Bases
EUROCAL '83, European Computer Algebra Conference, J. A. van Hulzen, editor
Lecture Notes in Computer Science 162
Springer-Verlag
pp. 137-145, 1983.
Buchberger B.
Grobner Bases: A Method in Symbolic Mathematics
Conference on Systems and Techniques of Analytical Computing and Their Applications in Theoretical Physics
Buchberger B.
Critical-Pair-Completion Algorithm for Finitely Generated Ideals in Rings
Logic and Machines: Decision Problems and Complexity, E. Borger, G. Hasenjaeger, D. Rodding, editors
Lecture Notes in Computer Science 171
Springer-Verlag
pp. 137-161, 1984.
Buchberger B.
A Survey on the Method of Grobner Bases for Solving Problems in Connection with Systems of Multivariate Polynomials
The Second International Symposium on Symbolic and Algebraic Computation by Computers
RIKEN, Wako-Shi, Saitama, 351-01, Japan
pp. 7-1--7-15, 1985.
Buchberger B.
Grobner Bases: An Algorithmic Method in Polynomial Ideal Theory
Recent Trends in Multidimensional Systems Theory, N. K. Bose and D. Reidel, editors
pp. 184-232, 1985.
Buchberger B.
Basic Features and Development of the Critical-Pair-Completion Procedure
Rewriting Techniques and Applications, J. P. Jouannaud, editor
Lecture Notes in Computer Science 202
Springer-Verlag
pp. 1-45, 1985.
Buchberger B.
History and Bais Features of the Critical-Pair-Completion Procedure
Journal of Symbolic Computation, vol. 3/1,2
pp. 3-38, 1987.
Buchberger B.
The Parallelization of Critical Pair/Completion Procedures on the L-Machines
Proceedings of the Japaneze Symposium on Functional Programming
pp. 54-61, 1987.
Buchberger B.
Applications of Grobner Bases in non-Linear Computational Geometry
Trends in Computer Algebra, R. Jansen, editor
Lecture Notes in Computer Science 296
Springer-Verlag
pp. 52-80, 1987.
Conti P. - Traverso C.
Buchberger's Algorithm and Integer Programming
AAECC-9, Lecture Notes in Computer Science
Springer-Verlag, 1991.
Cox D. - Little J. - O'Shea D.
Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra
Springer-Verlag, 1992
Faughre J.
Parallelization of Grobner Basis
Proceedings of PASCO'94
World Scientific, 1994
Faughre J. - Gianni P. - Lazard D. - Mora T.
Efficient Computation of Zero-Dimensional Grobner Bases by Change of Ordering
Journal of Symbolic Computation
1994.
Gebauer R. - Moller H.
On an Installation of Buchberger's Algorithm
Journal of Symbolic Computation vol. 6
pp. 275-286, 1988.
Giovini A. - Mora T. - Niesi G. - Robbiano L. - Traverso C.
One Sugar Cube, Please. Selection Strategies in the Buchberger Algorithm
Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation
ISSAC, S. M. Watt, editor
ACM Press, 1991.
Grabe, H. - Lassner W.
A Parallel Grobner Factorizer
Proceedings of PASCO'94
World Scientific, 1994
Senechaud P.
Implementation of a Parallel Algorithm to Compute a Grobner Basis on Boolean Polynomials
Computer Algebra and Parallelism
Academic Press
pp. 159-166, 1989.
Siegl K.
A Parallel Factorization Tree Grobner Basis Algorithm
Proceedings of PASCO'94
World Scientific, 1994
Vidal J.
The Computation of Grobner Bases on a Shared Memory Multiprocessor
Design and Implementation of Symbolic Computation Systems
Lecture Notes in Computer Science 429
Springer-Verlag, 1990.

Back to index page.