S-Space College of Natural Sciences (자연과학대학) Dept. of Mathematical Sciences (수리과학부) Theses (Master's Degree_수리과학부)
Analysis of the Grobner basis algorithms
그뢰브너 기저를 계산하는 알고리즘의 분석
- 자연과학대학 수리과학부
- 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
: : :
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.