New Strategies for Computing Grà¶bner Bases

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.