"Groebner Bases Algorithm 001.ps.gz" - читать интересную книгу автора

Gr"obner Bases Algorithm\Lambda Iyad A. Ajwa Zhuojun Liu Paul S. Wangy

Institute for Computational Mathematics Department of Mathematics & Computer Science

Kent State University Kent, Ohio 44242, U.S.A. fiajwa , zliu , [email protected]

February 28, 1995

----------------------------------------------------------------------------- Abstract. Gr"obner Bases are certain finite sets of multivariate polynomials. Gr"obner Bases Algorithm is a technique that provides algorithmic solutions to a variety of problems in commutative algebra and algebraic geometry. In this introductory tutorial, the theory of Gr"obner Bases is discussed in details, algorithms for computing a Gr"obner basis are presented, and several applications are investigated. -----------------------------------------------------------------------------

1 Introduction The origins of algebra and algorithms date back to the ninth century. Working on polynomial equations, the mathematician Mohammed Ibn Musa al-Khawarizmi wrote his famous book kitab al-jabr wa'l muqabala in Baghdad. The book discusses symbolic methods for solving polynomial equations. The words algebra and algorithms are actually the westernization of the words al-jabr and al-Khawarizmi'yah respectively [1]. Until the nineteen sixties, Algebra was concerned with constructive methods. With the discovery of computers and their development, algebraic algorithms have been recognized to play a central role in computer science. The recent advances in computer technology coupled with the ancient interest in algebraic algorithms have made it necessary to study computer related topics to algorithms, such as their efficiency, implementation, hardware and software needs and so on. This has lead to the establishment of Computer Algebra, a field of study that extends deeply into both Mathematics and Computer Science.

Over the years, new concepts and results have developed in the area of Computer Algebra and computer algebraists made significant contributions to the fields of Mathematics and Computer Science. Among these contributions, an outstanding example is the theory and algorithms for Gr"obner bases.

\Lambda ICM Techincal Reports Series (ICM-199502-00), February 1995.

yWork reported herein has been supported in part by the National Science Foundation under Grant CCR9201800

1

The concept of Gr"obner Bases was introduced by Bruno Buchberger (1965) in the context of his work on performing algorithmic computations in residue classes of polynomial rings. Buchberger's algorithm for computing Gr"obner bases is a powerful tool for solving many important problems in polynomial ideal theory. It has been extensively studied, developed, refined, and it has been implemented on most computer algebra systems.

This tutorial is divided into eight sections. We start by presenting mathematical definitions and notations necessary for understanding the theory of Gr"obner bases in Section 2. The important concept of monomial ordering is discussed in Section 3. The topic of polynomial reduction is the corner stone of the Gr"obner bases algorithm and is explained in Section 4. Buchberger's original algorithm and a modified version of it are given in Sections 5 and 6. Section 7 highlights some important applications of the Gr"obner basis algorithm in systems of polynomial equations in several variables. Concluding remarks are given in Section 8.

2 Mathematical Notations The theory of Gr"obner bases is centered around the concept of ideals generated by finite sets of multivariate polynomials. Studying polynomials is essential to understand the relationship between algebra and geometry. Therefore, we start our discussion by defining some basic algebraic structures.

Definition. A commutative ring hR; +; \Delta i is a set R with the two binary operations addition (+) and multiplication (\Delta ) defined on R such that hR; +i is a commutative group, (\Delta ) is commutative and associative, and the distributive law a\Delta (b+c) = a\Delta b+a\Delta c holds 8a; b; c 2 R.

Example. hZ; +; \Delta i is a commutative ring. Definition. Let hR; +; \Delta i be a commutative ring with a multiplicative identity. hR; +; \Delta i is called a field if every nonzero element of R has a multiplicative inverse in R.

Example. hQ; +; \Delta i, hR; +; \Delta i, hC; +; \Delta i are fields. However, hZ; +; \Delta i is not a field. Definition. Let N denote the non-negative integers. Let ff = (ff1; : : :; ffn) be a power vector in N n, and let x1; x2; : : : ; xn be any n variables. Then a monomial xff in x1; x2; : : : ; xn is defined as the product xff = xff11 \Delta xff22 \Delta \Delta \Delta xff

nn . Moreover, the total degree of the monomial xff

is defined as jffj = ff1 + \Delta \Delta \Delta + ffn.

Example. x5y2z, x4y3, y5, and x2z are monomials in x; y; z. They are of total degrees 8, 7, 5, and 3 respectively. In this tutorial, unless otherwise specified, all monomials will be in x1; x2; : : : ; xn.