Singular
https://www.singular.uni-kl.de/forum/

search of a grobner basis
https://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=1797		 Page 1 of 1
Author:  loup blanc [ Wed Feb 03, 2010 10:37 am ]
Post subject:  search of a grobner basis
Hi, I downloaded Singular but I cannot make use of this software. Before I used Maple to construct Grobner bases in commutative rings. Now I want to work on non commutative rings. For example I seek a grobner base for this example (non commutative):
variables: x,a
polynomials: a^2-a,x*a-a*x-x-2*x^2+3*x^3-5*x^4
Perhaps Singular uses only homogeneous polynomials. Then the problem is:
variables: x,k,a
polynomials: a^2-a*k,x*a*k^2-a*x*k^2-x*k^3-2*x^2*k^2+3*x^3*k-5*x^4.
How to write the orders ?
Thanks
Author:  Guest [ Wed Feb 03, 2010 2:42 pm ]
Post subject:  Re: search of a grobner basis
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
Page 1 of 1 All times are UTC + 1 hour [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/