New Strategies for Computing Gröbner Bases

Gameiro Simões, Bruno Manuel (2013) New Strategies for Computing Gröbner Bases. PhD thesis, University of Trento.

PDF - Doctoral Thesis
Available under License Creative Commons Attribution.



Gröbner bases are special sets of polynomials, which are useful to solve problems in many fields such as computer vision, geometric modeling, geometric theorem proving, optimization, control theory, statistics, communications, biology, robotics, coding theory, and cryptography. The major disadvantage of algorithms to compute Gröbner bases is that computations can use a lot of computer power. One of the reasons is the amount of useless critical pairs that the algorithm has to compute. Hence, a lot of effort has been put into developing new criteria to detect such pairs in advance. This thesis is devoted to describe efficient algorithms for the computation of Gröbner bases, with particular emphasis to those based on polynomial signatures. The idea of associating each polynomial with a signature on which the criteria and reduction steps depend, has become extremely popular in part due to its good performance. Our main result combines the criteria from Gao-Volny-Wang's algorithm with the knowledge of Hilbert Series. A parallel implementation of the algorithm is also investigated to improve the computational efficiency. Our algorithm is implemented in CoCoALib, a C++ free library for computations in commutative algebra.

Item Type:Doctoral Thesis (PhD)
Doctoral School:Mathematics
PhD Cycle:XXV
Subjects:Area 01 - Scienze matematiche e informatiche > INF/01 INFORMATICA
Area 01 - Scienze matematiche e informatiche > MAT/02 ALGEBRA
Repository Staff approval on:03 May 2013 09:11

Repository Staff Only: item control page