An analysis of inhomogeneous signature-based Gröbner basis computations

DOI10.1016/J.JSC.2013.08.001MaRDI QIDQ2437323zbMATHOpenAlexFDO

Authors Christian Eder

Publication date 3 March 2014

Published in Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

signature-based algorithmsF5GVWsugarG2VGVWHSsignature degreesugar degreeGrö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)

Abstract: In this paper we give an insight into the behaviour of signature-based Gr"obner basis algorithms, like F5, G2V or SB, for inhomogeneous input. On the one hand, it seems that the restriction to sig-safe reductions puts a penalty on the performance. The lost connection between polynomial degree and signature degree can disallow lots of reductions and can lead to an overhead in the computations. On the other hand, the way critical pairs are sorted and corresponding s-polynomials are handled in signature-based algorithms is a very efficient one, strongly connected to sorting w.r.t. the well-known sugar degree of polynomials.

Recommendations

• A survey on signature-based algorithms for computing Gröbner bases
• Signature-based algorithms to compute Gröbner bases
• Improving incremental signature-based Gröbner basis algorithms
• A new signature-based algorithms for computing Gröbner bases
• A new framework for computing Gröbner bases

Cites work

• scientific article; zbMATH DE number 1273640 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• A new incremental algorithm for computing Groebner bases
• An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
• Computing inhomogeneous Gröbner bases
• F5C: A variant of Faugère's F5 algorithm with reduced Gröbner bases
• Modifying Faugère's F5 algorithm to ensure termination
• On the cancellation rule in the homogenization
• Practical Gröbner basis computation
• Signature rewriting in Gröbner basis computation
• Signature-based algorithms to compute Gröbner bases
• The F5 criterion revised

Cited in

(7)

• Speeding up the GVW algorithm via a substituting method
• Computing inhomogeneous Gröbner bases
• An improvement over the GVW algorithm for inhomogeneous polynomial systems
• On affine tropical F5 algorithms
• A survey on signature-based algorithms for computing Gröbner bases
• On the computation of Gröbner bases for matrix-weighted homogeneous systems
• Improving incremental signature-based Gröbner basis algorithms

Describes a project that uses

Uses Software

• PoSSo
• F5C

This page was built for publication: An analysis of inhomogeneous signature-based Gröbner basis computations

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