Reducing the size and number of linear programs in a dynamic Gröbner basis algorithm

Abstract

The dynamic algorithm to compute a Gröbner basis is nearly twenty years old, yet it seems to have arrived stillborn; aside from two initial publications, there have been no published followups. One reason for this may be that, at first glance, the added overhead seems to outweigh the benefit; the algorithm must solve many linear programs with many linear constraints. This paper describes two methods of reducing the cost substantially, answering the problem effectively.

11 figures, of which half are algorithms; submitted to journal for refereeing, December 2012