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

DOI10.1016/J.JSC.2013.08.001zbMATH Open1311.13037arXiv1203.6186OpenAlexW2073299143MaRDI QIDQ2437323FDOQ2437323

Authors: Christian Eder 

Publication date: 3 March 2014

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

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.

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

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

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)

Cites Work

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

Cited In (7)

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

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)