Analysis of the Grobner basis algorithms
그뢰브너 기저를 계산하는 알고리즘의 분석

Cited 0 time in Web of Science Cited 0 time in Scopus
자연과학대학 수리과학부
Issue Date
서울대학교 대학원
학위논문 (석사)-- 서울대학교 대학원 : 자연과학대학 수리과학부, 2018. 8. 현동훈.
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.
Files in This Item:
Appears in Collections:
College of Natural Sciences (자연과학대학)Dept. of Mathematical Sciences (수리과학부)Theses (Master's Degree_수리과학부)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.