Hi, Singular has various functionalities for computing non-commutative Groebner bases.
It depends on what do you want to compute, which way to choose.
Analyzing your relations
a^2-a and
x*a-a*x-x-2*x2+3*x^3-5*x^4, there are two ways possible:
Method 1 "going via G-algebras" One can construct first a G-algebra (see Singular Manual) in {x,a} subject to relations x*a = a*x + x + 2*x2-3*x^3+5*x^4
(
Note: x^i*a^j will be rewritten according to this relation, while a^i*x^j is treated as a standard monomial!)
with a monomial ordering, satisfying a>>x (that is a is bigger than any power of x). Let us call this algebra A1.
Code:
ring a1 = 0,(a,x),lp; // lp = lex ordering
poly p1 = x + 2*x2-3*x^3+5*x^4;
def A1 = nc_algebra(1,p1); setring A1;
A1; // print the non-comm relation as well
Then you define a two-sided ideal, generated by a^2-a and compute its two-sided Groebner basis.
Code:
ideal Q = a^2-a;
option(redSB); // in order to compute reduced Groebner basis
Q = twostd(Q); // two-sided Groebner basis
Q; // can be regarded as Groebner basis of the ideal of all your relations
vdim(Q); // since A1/Q looks finite-dimensional, vdim computes this or returns -1 in case of inf. dim
// as we see, the ring A1/Q is 9-dimensional over basefield
kbase(Q); // returns a monomial basis
If you wish to perform further computations in the factor ring (which is of type
qring), let's call it A2, do the following:
Code:
qring A2 = Q;
A2;
Now, assume you'd like to know the left Groebner basis of a left ideal, generated by x^2
(it's K-dimension will be, of course, finite, since A2 is finite dimensional:
Code:
ideal I2 = x^2; I2 = std(I2);
vdim(I2); // you see it's 3
kbase(I2); // you see the mononial basis
Method 2 "working in the free algebra" We have an implementation of so-called "Letterplace Paradigm" by La Scala and Levandovskyy
(see Singular Manual: Noncommutative Subsystem: Letterplace), where your objects
live in a big and very special commutative ring.
You can first set a degree bound for computations (up to which to compute), in this case, say, 10.
Then the procedure
makeLetterplaceRing creates a commutative letterplace ring for the homogenized case.
Code:
LIB "freegb.lib";
ring r = 0,(a,x,k),Dp; // Dp = deg lex ordering
int d = 10; // degree bound
def R = makeLetterplaceRing(d);
setring R;
R has now variables a(1),..,a(10),x(1),..,x(10),k(1),..,k(10).
Now you have to write your input polynomials in a letterplace way, that is as follows: a "word" w1 w2 .. wN
(where wI are variables) will be written as commutative monomial w1(1) w2(2) .. wN(N).
Note: the indices MUST be continuously increasing from 1 to the degree of a monomial. In your case one writes
Code:
ideal I = a(1)*a(2) - a(1)*k(2),
x(1)*a(2)*k(3)*k(4)-a(1)*x(2)*k(3)*k(4)-x(1)*k(2)*k(3)*k(4)-2*x(1)*x(2)*k(3)*k(4)+3*x(1)*x(2)*x(3)*k(4)-5*x(1)*x(2)*x(3)*x(4);
// DON'T forget that the homogenizing variable k
// commutes with a and x : add commutator relations
ideal C = a(1)*k(2)-k(1)*a(2), x(1)*k(2)-k(1)*x(2);
I = I+C;
Now you set the options and run Letterplace Groebner basis:
Code:
option(redSB); option(redTail); option(prot);
ideal J = system("freegb",I,d,nvars(r));
J;
Actually even increasing degree bound d, with respect to the ordering above the Groebner basis is infinite
(this happens often in homogenized examples). But you can see some of the real elements by doing e.g. the following:
Code:
ideal K = k(1)-1,k(2)-1,k(3)-1,k(4)-1,k(5)-1,k(6)-1,k(7)-1,k(8)-1; // dehomogenizing with respect to k
K = std(K);
J = NF(J,K); // J dehomogenized
In particular, the elements x*a*x-x*x*a, a*x*a-a*x, a*x*x-2*x*a*x+x*x*a = a*x*x-x*x*a can be seen from the partial dehomogenization.
Indeed, we have already an experimental version of nonhomogeneous Groebner basis without homogenization.
However, it is not yet a part of the official distribution of Singular, you need the new version of "freegb.lib",
which I can send you via email. The code will then look as follows:
Code:
LIB "freegb.lib";
ring r = 0,(a,x),dp;
int d = 10; // degree bound
def R = makeLetterplaceRing2(d);
setring R;
ideal I = a(1)*a(2) - a(1), x(1)*a(2)-a(1)*x(2)-x(1)-2*x(1)*x(2)+3*x(1)*x(2)*x(3)-5*x(1)*x(2)*x(3)*x(4);
option(redSB); option(redTail); option(prot);
ideal J = system("freegb",I,d,nvars(r));
As we can see, this Groebner basis is finite. By using the library "freeqa.lib" (under development
by my student Grischa Studzinski) you can compute the K-dimension of the factor algebra (which is 9 as before)
as well as a monomial K-basis (which is {1,a,x,ax,xa,x^2,x^2*a, x^3, x^3*a}).
With best regards,
Viktor Levandovskyy
Login
Register
Forum FAQ
Forum Search
