Debian Codegraph @

tests/inputs/Buchberger.cocoa5

raw
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]);