A generalized criterion for signature related Gröbner basis algorithms

DOI10.1145/1993886.1993936MaRDI QIDQ5254191zbMATH OpenOpenAlexFDO

Authors Yao Sun, Dingkang Wang

Publication date 9 June 2015

Published in Proceedings of the 36th international symposium on Symbolic and algebraic computation (Search for Journal in Brave)

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

zbMATH Keywords

F5generalized criterionGröbner basissignature related algorithm

Mathematics Subject Classification ID

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

Abstract: A generalized criterion for signature related algorithms to compute Gr"obner basis is proposed in this paper. Signature related algorithms are a popular kind of algorithms for computing Gr"obner basis, including the famous F5 algorithm, the extended F5 algorithm and the GVW algorithm. The main purpose of current paper is to study in theory what kind of criteria is correct in signature related algorithms and provide a generalized method to develop new criteria. For this purpose, a generalized criterion is proposed. The generalized criterion only relies on a general partial order defined on a set of polynomials. When specializing the partial order to appropriate specific orders, the generalized criterion can specialize to almost all existing criteria of signature related algorithms. For {em admissible} partial orders, a complete proof of the correctness of the algorithm based on this generalized criterion is also presented. This proof has no extra requirements on the computing order of critical pairs, and is also valid for non-homogeneous polynomial systems. More importantly, the partial orders implied by existing criteria are admissible. Besides, one can also check whether a new criterion is correct in signature related algorithms or even develop new criteria by using other admissible partial orders in the generalized criterion.

Recommendations

• A new signature-based algorithms for computing Gröbner bases
• Extended \(F_5\) criteria
• The F5 criterion revised
• scientific article; zbMATH DE number 2151220
• Signature-based algorithms to compute Gröbner bases

Cited in

(17)

• A survey on signature-based algorithms for computing Gröbner bases
• Speeding up the GVW algorithm via a substituting method
• An improvement for GVW
• Signature Gröbner bases, bases of syzygies and cofactor reconstruction in the free algebra
• A new signature-based algorithms for computing Gröbner bases
• Involutive bases algorithm incorporating F\(_5\) criterion
• GVW algorithm over principal ideal domains
• Simple signature based iterative algorithm for calculation of Gröbner bases
• A new framework for computing Gröbner bases
• A new proof for the correctness of the F5 algorithm
• Invariant \(\mathrm G^2\mathrm V\) algorithm for computing SAGBI-Gröbner bases
• Improving incremental signature-based Gröbner basis algorithms
• An improvement over the GVW algorithm for inhomogeneous polynomial systems
• Axioms for a theory of signature bases
• An Hilbert-driven strategy for signature-based Gröbner basis algorithms
• Signature-based standard basis algorithm under the framework of GVW algorithm
• A signature-based algorithm for computing Gröbner bases over principal ideal domains

Describes a project that uses

Uses Software

• F5C

This page was built for publication: A generalized criterion for signature related Gröbner basis algorithms

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