| 1 |
define Buchberger(F) |
| 2 |
-- Make all monic for (sometimes) nicer GB :) |
| 3 |
G := [monic(f) | f in F]; |
| 4 |
r := len(G); |
| 5 |
B := [x in tuples(1..r, 2) | 1 <= x[1] and x[1] < x[2] and x[2] <= r]; |
| 6 |
while B <> [] do |
| 7 |
p := B[1]; |
| 8 |
remove(ref B, 1); |
| 9 |
gj := G[p[1]]; |
| 10 |
gk := G[p[2]]; |
| 11 |
|
| 12 |
// Optimization: Skip if LTs are coprime |
| 13 |
if IsCoprime(LT(gj), LT(gk)) then |
| 14 |
continue; |
| 15 |
endif; |
| 16 |
|
| 17 |
t := lcm(LT(gj), LT(gk)); |
| 18 |
Sjk := (t / LM(gj)) * gj - (t / LM(gk)) * gk; |
| 19 |
R := NR(Sjk, G); |
| 20 |
if R <> 0 then |
| 21 |
// Append monic for (sometimes) nicer GB :) |
| 22 |
append(ref G, monic(R)); |
| 23 |
r := len(G); |
| 24 |
B := concat(B, [[i, r] | i in 1..(r-1)]); |
| 25 |
endif; |
| 26 |
endwhile; |
| 27 |
return G; |
| 28 |
enddefine; -- Buchberger |
| 29 |
|
| 30 |
define BuchbergerOnIdeal(I) |
| 31 |
return Buchberger(gens(I)); |
| 32 |
enddefine; -- BuchbergerOnIdeal |
| 33 |
|
| 34 |
define TestBuchberger(F) |
| 35 |
println "===== INPUT: ", F, " ====="; |
| 36 |
B1 := Buchberger(F); |
| 37 |
B2 := GBasis(ideal(F)); |
| 38 |
println "Basis: ", B1; |
| 39 |
eq := EqSet(B1, B2); |
| 40 |
println "Equals? ", eq; |
| 41 |
if not(eq) then |
| 42 |
// If the reduced GBs are equal, the Buchberger-computed GB |
| 43 |
// is most likely also a correct one. |
| 44 |
req := ReducedGBasis(ideal(B1)) = ReducedGBasis(ideal(B2)); |
| 45 |
println "Red GB eq? ", req; |
| 46 |
if not(req) then println "Correct: ", B2; endif; |
| 47 |
endif; |
| 48 |
enddefine; -- TestBuchberger |
| 49 |
|
| 50 |
/* |
| 51 |
Test cases can be found here! |
| 52 |
First, some using a "normal" term order. |
| 53 |
Then, some using an elimination ordering. |
| 54 |
*/ |
| 55 |
|
| 56 |
use QQ[x,y,z], DegRevLex; |
| 57 |
TestBuchberger([x^10,x^8*y^6,x^7*y^7,x^6*y^8,y^10]); |
| 58 |
TestBuchberger([x^3-3,y^5-5,z^7-7]); |
| 59 |
TestBuchberger([5*y^2+4*y*z-2*y-4,4*y^2-3*y*z+5*z^2-5*z]); |
| 60 |
TestBuchberger([8*x^3+x^2*y-2*z^2+4,7*x^3+6*x^2*z-5*x*y*z-5*y^2]); |
| 61 |
TestBuchberger([x^5+x*y^4+y^2*z^3+z^5,x^4*y+x^3*y^2+x^4*z+x^2*z^3]); |
| 62 |
use QQ[x,y,z], Lex; |
| 63 |
println "===== INPUT: ", [x^2*y*z+x*y^3*z-1,x^4*y*z-1,x*y^4+x*y*z-1] , " ====="; |
| 64 |
println "Basis: ", Buchberger([x^2*y*z+x*y^3*z-1,x^4*y*z-1,x*y^4+x*y*z-1]); |