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)|
|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