The Termination of Algorithms for Computing Gröbner Bases

Details The Termination of Algorithms for Computing Gröbner Bases The Termination of Algorithms for Computing Gröbner Bases

2012-02-16

arxiv.org/abs/1202.3524v5

Mathematics

Commutative Algebra

20 pages. We make the Theorem 12 self-contained and refine the proof for conciseness; For 3 different version of the F5 algori

Scientific paper

The F5 algorithm is generally believed as one of the fastest algorithms for computing Gr\"{o}bner bases. However, its termination problem is still unclear. Recently, an algorithm GVW and its variant GVWHS have been proposed, and their efficiency are comparable to the F5 algorithm. In the paper, we clarify the concept of an admissible module order. For the first time, the connection between the reducible and rewritable check is discussed here. We show that the top-reduced S-Gr\"{o}bner basis must be finite if the admissible monomial order and the admissible module order are compatible. This paper presents a complete proof of the termination and correctness of the GVWHS algorithm. What is more, it can be seen that the GVWHS is in fact an F5-like algorithm. Different from the GVWHS algorithm, the F5B algorithm may generate redundant sig-polynomials. Taking into account this situation, we prove the termination and correctness of the F5B algorithm. And we notice that the original F5 algorithm slightly differs from the F5B algorithm in the insertion strategy on which the F5-rewritten criterion is based. Exploring the potential ordering of sig-polynomials computed by the original F5 algorithm, we propose an F5GEN algorithm with a generalized insertion strategy, and prove the termination and correctness of it. Therefore, we have a positive answer to the long standing problem of proving the termination of the original F5 algorithm.

Affiliated with

Also associated with

No associations

Rating

The Termination of Algorithms for Computing 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 The Termination of Algorithms for Computing Gröbner Bases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Termination of Algorithms for Computing Gröbner Bases will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-125070