Computer Science – Symbolic Computation
Scientific paper
2011-06-24
Computer Science
Symbolic Computation
This paper is a substantially expanded version of the paper entitled "A Generalized Criterion for Signature Related Gr\"obner
Scientific paper
A generalized criterion for signature-based algorithms to compute Gr\"obner bases is proposed in this paper. This criterion is named by "generalized criterion", because it can be specialized to almost all existing criteria for signature-based algorithms which include the famous F5 algorithm, F5C, extended F5, G$^2$V and the GVW algorithm. The main purpose of current paper is to study in theory which kind of criteria is correct in signature-based algorithms and provide a generalized method to develop new criteria. For this purpose, by studying some key facts and observations of signature-based algorithms, a generalized criterion is proposed. The generalized criterion only relies on a 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-based algorithms. For {\em admissible} partial orders, a proof is presented for the correctness of the algorithm that is based on this generalized criterion. And the partial orders implied by the criteria of F5 and GVW are also shown to be admissible. More importantly, the generalized criterion provides an effective method to check whether a new criterion is correct as well as to develop new criteria for signature-based algorithms.
Sun Yao
Wang Dingkang
No associations
LandOfFree
A Generalized Criterion for Signature-based Algorithms to Compute Gröbner Bases 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-based Algorithms to Compute Gröbner Bases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Generalized Criterion for Signature-based Algorithms to Compute Gröbner Bases will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-393841