Unrestricted dynamic Gröbner Basis algorithms

• Ano de defesa: 2019
• Autor(a) principal: Langeloh, Gabriel Mattos
• Orientador(a): Ritt, Marcus Rolf Peter
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Palavras-chave em Português: Algoritmos; Algoritmo dinâmico
• Palavras-chave em Inglês: Gröbner bases; Dynamic algorithm; Monomial ordering
• Link de acesso: http://hdl.handle.net/10183/194287

Bases de Gröbner são uma ferramenta necessária para resolver diversos problemas envolvendo ideais polinomiais, incluindo aplicações como resolução de sistemas polinomiais não-lineares, programação inteira e criptografia. Algoritmos tradicionais de cálculo de Bases de Gröbner são estáticos, no sentido que eles recebem uma ordem monomial como entrada e essa ordem é então mantida fixa durante toda a execução do algoritmo. Algoritmos dinâmicos, pelo contrário, permitem que a ordem monomial mude para gerar bases menores e, espera-se, realizar menos reduções polinomiais. Com apenas uma exceção, todos os algoritmos dinâmicos previamente propostos são restritos, o que significa que uma vez que eles escolhem um monômio líder para um certo polinômio, essa escolha não pode ser desfeita. No presente trabalho, exploramos algoritmos dinâmicos irrestritos, estudando a relação entre ordens monomiais e poliedros de Newton e propondo quatro novos algoritmos irrestritos que evitam avaliar muitas ordens usando um conceito de vizinhança para ordens monomiais. Também propomos uma nova heurística, chamada de heurística Mista, para a avaliação de ordens monomiais em algoritmos dinâmicos. Nossos experimentos mostram que apesar de os algoritmos restritos terem melhor desempenho em termos de tempo de execução, nossos algoritmos irrestritos encontram ordens que levam a Bases de Gröbner menores para muitas instâncias e significativamente reduzem o grau máximo dos polinômios na base em média. Adicionalmente, fornecemos uma comparação entre as heurísticas de Hilbert e Betti, previamente propostas, e nossa heurística Mista, mostrando que ela tem desempenho melhor que a heurística de Betti na maioria dos aspectos e é competitiva com a heurística de Hilbert em geral.