Welcome to the resource topic for 2010/641
Title:
A new algorithm for computing Groebner bases
Authors: Shuhong Gao, Frank Volny IV, Mingsheng Wang
Abstract:Buchberger’s algorithm for computing Groebner bases was introduced in 1965, and subsequently there have been extensive efforts in improving its efficiency. Major algorithms include F4 (Faugère 1999), XL (Courtois et al. 2000) and F5 (Faugère 2002). F5 is believed to be the fastest algorithm known in the literature. Most recently, Gao, Guan and Volny (2010) introduced an incremental algorithm (G2V) that is simpler and several times faster than F5. In this paper, a new algorithm is presented that can avoid the incremental nature of F5 and G2V. It matches Buchberger’s algorithm in simplicity and yet is more flexible. More precisely, given a list of polynomials, the new algorithm computes simultaneously a Groebner basis for the ideal generated by the polynomials and a Groebner basis for the leading terms of the syzygy module of the given list of polynomials. For any term order for the ideal, one may vary signature orders (i.e. the term orders for the syzygy module). Under one signature order, the new algorithm specializes to the G2V, and under another signature order, the new algorithm is several times faster than G2V, as indicated by computer experiments on benchmark examples.
ePrint: https://eprint.iacr.org/2010/641
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .