Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10316/103132
Título: | Predicting the perfomance of Buchberger`s algorithm | Outros títulos: | Prever o desempenho do algoritmo de Buchberger | Autor: | Cruz, Ana Maria Marques | Orientador: | Gouveia, João Eduardo da Silveira | Palavras-chave: | Bases de Gröbner; Algoritmo Buchberger; Regressão Linear; Redes Neuronais; Ideais; Gröbner Basis; Buchberger's Algorithm; Linear Regression; Neural Networks; Ideals | Data: | 30-Set-2022 | Título da revista, periódico, livro ou evento: | Predicting the perfomance of Buchberger`s algorithm | Local de edição ou do evento: | Departamento de Matemática da Universidade de Coimbra | Resumo: | 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. |
Descrição: | Dissertação de Mestrado em Matemática apresentada à Faculdade de Ciências e Tecnologia | URI: | https://hdl.handle.net/10316/103132 | Direitos: | openAccess |
Aparece nas coleções: | UC - Dissertações de Mestrado |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
MScMathDiss_AnaCruz.pdf | 1.35 MB | Adobe PDF | Ver/Abrir |
Visualizações de página
61
Visto em 27/ago/2024
Downloads
75
Visto em 27/ago/2024
Google ScholarTM
Verificar
Este registo está protegido por Licença Creative Commons