Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In an upcoming exam we have to do Gröbnber-Basis computation with Buchberger's algorithm. A typical example looks like this:

$$ \langle f_1,f_2 \rangle $$

Then I compute the S-Polynomial $S(f_1,f_2)$. Most of the time $S(f_1,f_2)$ is an ugly expression so I use linear combinations of $\langle f_1, f_2, S(f_1,f_2)\rangle$ and obtain a new representation of the ideal with nice polynomials $\langle f_1',f_2',f_3' \rangle$.

Now, I have to restart Buchberger's algorithm because I have changed the ideal representation and compute $S(f_1',f_2'), S(f_1',f_3') \dots$. Usually $\langle f_1',f_2',f_3' \rangle$ is a valid Gröber basis already. But to compute the three (or more) S-Polynomials takes a lot of time. Is there are a (fast computable) criteria to check whether a given basis is already a Gröbner-Basis and to abort the computation?

share|improve this question
1  
I believe the answer you are looking for is in these lecture notes by Victor Adamchik. I could be incorrect, however, my experiences with Gröbner Bases is mostly computational. –  process91 Sep 2 '12 at 15:06

1 Answer 1

Given generators $f_1, \dots, f_n$ for an ideal $I$, you can reduce each $S$-polynomial $S(f_i, f_j)$ using the $f_1, \dots, f_n$. Reducing here means repeatedly canceling the highest degree term of $S(f_i, f_j)$ (in whatever admissible monomial ordering you are using) by subtracting a suitable multiple of one of the $f_k$ (i.e., multiply by $f_k$ by some monomial such that its highest terms equal that of $S(f_i, f_j)$ and subtract; repeat until the leading term of what is left of $S(f_i, f_j)$ is not a multiple of the leading term of any of the $f_k$). If all $S$ polynomials reduce to 0, your original generators form a Gröber basis already.

In fact, this is how you would generally compute a Gröber basis: you keep adding reductions of $S$-polynomials to the set of generators until they all reduce to 0. (And in between you simplify the generators by reducing using a newly computed reduction of an $S$-polynomial).

share|improve this answer
    
I think what your describing is the cancellation criterion of Buchberger's algorithm. I was trying to avoid that computation and was looking for some kind of short cut to proof that the computation can be stopped at this point. I am starting to think that the answer is that there is no such short-cut. –  joachim Dec 10 '13 at 16:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.