A Generalized Criterion for Signature Related Gröbner Basis Algorithms

Details A Generalized Criterion for Signature Related Gröbner Basis Algorithms A Generalized Criterion for Signature Related Gröbner Basis Algorithms

2011-01-18

arxiv.org/abs/1101.3382v2

Computer Science

Symbolic Computation

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A Generalized Criterion for Signature Related Gröbner Basis Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Generalized Criterion for Signature Related Gröbner Basis Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Generalized Criterion for Signature Related Gröbner Basis Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-286276