Analysis of the Grobner basis algorithms

Abstract

In algebraic geometry, many problems related to multivariate polynomial systems

such as the ideal membership problem and the elimination have been

studied. To solve multivariate polynomial systems, Grobner basis method

have been used. A multivariate polynomial system is a generator of an ideal,

but in general it may not be a Grobner basis. In order to solve the problem,

Bruno Buchberger suggested a necessary condition the Grobner basis has to

satisfy and an algorithm nding the Grobner basis. However, this algorithm

has a great computational cost for reducing polynomials. For many years,

Buchberger's algorithm has been studied and improved. One of them, the

F4 algorithm, is designed to simultaneously perform the process of reducing

polynomials with matrices. Another algorithm, the F5 algorithm, is designed

to avoid the process of reducing polynomials if the multivariate polynomial

system satises a special condition. There is also an XL algorithm that is

used when a multivariate polynomial system is a basis for a zero-dimensional

ideal. This algorithm is based on the fact that the intersection of the zerodimensional

ideal and subring k[xi] of the polynomial ring k[x1

: : :

xn] always

has non-zero elements.

The algorithms introduced above treat newly occurring polynomial of dierent

degree in the same way. However, Jintai Ding suggested a new approach

focusing on the lowest degree polynomial, which is called mutant polynomial,

and as a result, improved the algorithms.

This thesis introduces each algorithms and their main idea.We also introduce

an improved algorithm using mutant polynomials proposed by Jintai Ding.

Finally, we observe the

ow of ve algorithms through three examples and

compare algorithms to investigate strength and weakness of each algorithm.