Monday, February 24, 2014 - 15:05
1 hour (actually 50 minutes)
Buchberger (1965) gave the first algorithm for computing Groebner bases and introduced some simple criterions for detecting useless S-pairs. Faugere (2002) presented the F5 algorithm which is significantly much faster than Buchberger's algorithm and can detect all useless S-pairs for regular sequences of homogeneous polynomials. In recent years, there has been extensive effort trying to simply F5 and to give a rigorous mathematical foundation for F5. In this talk, we present a simple new criterion for strong Groebner bases that contain Groebner bases for both ideals and the related 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 and a simple proof of finite termination of the algorithm. This is a joint work with Frank Volny IV (National Security Agency) and Mingsheng Wang (Chinese Academy of Sciences).