Predicting zero reductions in Gröbner basis computations

DOI10.1145/2631948.2631968zbMATH Open1346.13058arXiv1404.0161OpenAlexW2006868715MaRDI QIDQ2819720FDOQ2819720

Authors: Christian Eder 

Publication date: 29 September 2016

Published in: Proceedings of the 2014 Symposium on Symbolic-Numeric Computation (Search for Journal in Brave)

Abstract: Since Buchberger's initial algorithm for computing Gr"obner bases in 1965 many attempts have been taken to detect zero reductions in advance. Buchberger's Product and Chain criteria may be known the most, especially in the installaton of Gebauer and M"oller. A relatively new approach are signature-based criteria which were first used in Faug`ere's F5 algorithm in 2002. For regular input sequences these criteria are known to compute no zero reduction at all. In this paper we give a detailed discussion on zero reductions and the corresponding syzygies. We explain how the different methods to predict them compare to each other and show advantages and drawbacks in theory and practice. With this a new insight into algebraic structures underlying Gr"obner bases and their computations might be achieved.

Full work available at URL: https://arxiv.org/abs/1404.0161

Recommendations

• scientific article; zbMATH DE number 2151220
• scientific article; zbMATH DE number 1263375
• Signature-based algorithms to compute Gröbner bases
• A survey on signature-based algorithms for computing Gröbner bases
• The F5 criterion revised

zbMATH Keywords

signaturesF5GVWGröbner basis

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Cited In (4)

• Linear algebra to compute Syzygies and Gröbner bases
• A survey on signature-based algorithms for computing Gröbner bases
• Tangent complexes and the Diamond Lemma
• Detecting unnecessary reductions in an involutive basis computation

Uses Software

• SINGULAR
• F5C

This page was built for publication: Predicting zero reductions in Gröbner basis computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2819720)