Abstract
Polynomial systems are ubiquitous in Mathematics, Sciences and Engineerings, and Groebner basis theory is one of the most powerful tools for solving polynomial systems from practice. Buchberger (1965) gave the first algorithm for computing Groebner bases and introduced some simple criteria for detecting useless S-pairs. Faugere (2002) introduced signatures and rewritten rules to detect useless S-pairs, and his F5 algorithm is significantly much faster than Buchberger's algorithm. In the last ten years or so, there has been extensive effort trying to modify F5 in order to have simpler algorithms that work for arbitrary sequence of polynomials (not necessarily homogeneous) and have rigorous proofs for correctness and finite termination.
In this talk, we present a new framework that underlies an algorithmic foundation for computing Groebner bases for both ideals and the related syzygy modules (the latter is useful for computing free resolutions). We give a simple criterion for strong Groebner bases that contain Groebner bases for both ideals and syzygy modules. This criterion can detect all useless J-pairs (without performing any reduction) for any sequence of polynomials, thus yielding an efficient algorithm for computing Groebner bases. All the rewritten rules in the literature can now be easily explained by this criterion. This is a joint work with Frank Volny IV (National Security Agency) and Mingsheng Wang (Chinese Academy of Sciences).