Unrestricted dynamic Gröbner Basis algorithms

Abstract

Gröbner bases are a necessary tool to solve many problems involving polynomial ideals, including applications such as nonlinear polynomial system solving, integer programming and cryptography. Traditional Gröbner Basis algorithms are static, in the sense that they receive a monomial order as input and it is fixed during the entire execution of the algorithm. Dynamic algorithms, in contrast, allow this monomial ordering to change to generate smaller output bases and, hopefully, fewer polynomial reductions. All but one of the previously proposed dynamic algorithms are restricted, meaning that once they choose a leading monomial for a certain polynomial, that choice cannot be unmade. In this work, we focus on exploring unrestricted dynamic algorithms, studying the relation of monomial orderings to Newton polyhedra and proposing four new unrestricted algorithms that avoid evaluating too many monomial orderings by using a neighborhood construction for monomial orders. We also propose a new heuristic, called the Mixed heuristic, for monomial order evaluation in dynamic algorithms. Our experiments show that although the restricted algorithms perform better with respect to running time, our unrestricted algorithms find orders that lead to smaller Gröbner Bases for many instances and significantly lower degree polynomials in average. Additionally, we provide a comparison between the previously defined Hilbert and Betti heuristics and our Mixed heuristic, showing it performs better than the Betti heuristic in most aspects and is competitive with the Hilbert heuristic overall.

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.