Predicting the perfomance of Buchberger`s algorithm

Abstract

As bases de Gröbner são um conceito fundamental em álgebra computacional. Desde a criação desta teoria, em 1949, por Wolfgang Gröbner, elas tornaram-se numa ferramenta importante emqualquer área onde exista computação polinomial, tanto na teoria como na prática. Embora se tenham demonstrado extremamente úteis, o seu cálculo é muito pesado em certos casos. O primeiro algoritmo desenvolvido para calcular estas bases é chamado Algoritmo de Buchberger, que ainda é um dos algoritmos mais utilizados para esse fim. Como passo preliminar para melhorar a eficiência do algoritmo, gostaríamos de poder prever, dado um ideal, quão complicado é calcular a respetiva base de Gröbner usando o Algoritmo de Buchberger. Nesta dissertação, abordamos precisamente esta questão, seguindo o trabalho recente de Mojsilovic, Peifer e Petrovic. Criamos um dataset que consiste em algumas distribuições de ideais binomiais e tóricos. Algumas propriedades dos mesmos foram estudadas de forma a procurar uma correlação entre essas características e o número de adições polinomiais. Depois introduzimos e aplicamos ferramentas de regressão linear e um modelo de rede neuronal simples para tentar prever o número de iterações necessárias usando as caracteristicas dos ideais definidas. De seguida, é usado redes neuronais recorrentes, para estudar a relação entre os expoentes dos ideais e o número de adições polinomiais. A performance tos três modelos é comparada e mostramos que existe uma melhoria considerável usando redes neuronais recurrentes, e que concluímos é possível prever o número de adições polinomiais, em alguns casos.

Gröbner bases are a fundamental concept in computational algebra. Since the creation of the theory behind them in 1949, by Wolfgang Gröbner, they became an important tool in any area where polynomial computations play a part, both in theory and in practice. Although they have proved to be very useful, their calculation is very expensive in certain cases. The first algorithm ever developed to compute these bases is the so-called Buchberger’s Algorithm and is still one of the most commonly used algorithms for this purpose. As a preliminary step in improving the efficiency of the algorithm, one would like to be able to predict, given an ideal, how complicated it is to compute its Gröbner basis using Buchberger’s Algorithm. In this dissertation, we address precisely this issue, following the work of Mojsilovic, Peifer and Petrovic. We create a dataset consisting of some binomial and toric distributions. Some of their properties were studied in order to seek the relationship between these characteristics and the number of polynomial additions. Then we introduce linear regression and a simple neural network model to try to predict the number of iterations using the ideals properties. Then, it is used a recurrent neural network to study the relationship between the exponents of ideals and that of polynomial additions is studied. The performance of the three models is compared and we show that there is a considerable improvement when using a recurrent neural network model and conclude that we are able to predict the number of polynomial additions, in some cases.