A survey on signature-based algorithms for computing Gröbner bases. (May 2017)

• Record Type: Journal Article
• Authors: Eder, Christian; Faugère, Jean-Charles
• Is Part Of: Journal of symbolic computation. Volume 80:Part 3(2017)
• Page Start: 719
• Page End: 784
• Publication Date: 2017-05
• Subjects: Gröbner bases -- F5 -- GVW -- Signature-based algorithms -- Syzygies; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2016.07.031
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: In 1965 Buchberger introduced an algorithmic approach to compute Gröbner bases. Later on, he and many others presented various attempts to improve the computation by removing useless elements a priori. One approach, initiated by Gebauer, Möller, Mora and Traverso in the 1990s, is to keep track of the corresponding syzygies which is related to the topic of this survey: signature-based algorithms for Gröbner bases. This area was initiated by Faugère's F5 algorithm in 2002. The general idea of signatures is to keep track of the history of the computation with a minimal overhead and to exploit this information to detect redundant elements. Here we give a summary of the literature on signature-based algorithms and show how to classify known algorithms by 3 different orderings. For this we give translations between different notations and show the relationships (differences and similarities) among many approaches. Moreover, we give a general description of how the idea of signatures is quite natural when performing the reduction process using linear algebra. We hope that this survey would help to outline this field of active research.