next | previous | forward | backward | up | top | index | toc | Macaulay2 website
ThreadedGB :: tgb

tgb -- threaded Groebner bases

Synopsis

Description

Threaded Groebner basis uses Tasks to compute a Groebner basis of I or ideal L using $n$ threads.

i1 : R = ZZ/101[x,y,z, MonomialOrder=>Lex];
i2 : I = ideal {2*x + 10*y^2*z, 8*x^2*y + 10*x*y*z^3, 5*x*y^3*z^2 + 9*x*z^3, 9*x*y^3*z + 10*x*y^3};

o2 : Ideal of R
i3 : H = tgb(I,4)

                                      2 8
o3 = HashTable{((((0-1)-2)-2)-2) => 9y z    }
                                   3 6
               (((0-1)-2)-2) => 13y z
                                  2 9
               (((0-1)-3)-2) => 9y z
                              4 4     3 7
               ((0-1)-2) => 9y z  - 6y z
                                3 7      3 6
               ((0-1)-3) => - 6y z  + 27y z
                             5 2      3 4
               (0-1) => - 25y z  - 19y z
                             3 5     2 4
               (0-2) => - 24y z  + 9y z
                           5       3 4
               (0-3) => 28y z - 24y z
                           3 4
               (1-2) => 21y z
                           2 4
               (2-3) => -9y z
                            2
               0 => 2x + 10y z
                      2           3
               1 => 8x y + 10x*y*z
                        3 2       3
               2 => 5x*y z  + 9x*z
                        3         3
               3 => 9x*y z + 10x*y

o3 : HashTable

The keys of the hashtable are meaningful; for example, the polynomial with key ((0-2)-1) in the hashtable tgb(L,n) is the remainder upon division of the S-polynomial $(g, I_1)$, where $g$ is calculated from the S-pair $(I_0, I_2)$. For this reason, we say that the key communicates the "lineage" of the resulting polynomial. (See ThreadedGB.)

Note that the keys in the hash table are strings, and the keys of input polynomials are 0..#L, as in the following example.

i4 : H#"(0-1)"

          5 2      3 4
o4 = - 25y z  - 19y z

o4 : R

Some may be curious with respect to how tgb works.

The starting basis $L$ (the input list L or L=gens I) populate the 0..#L entries of a MutableHashTable $G$. The method creates all possible S-polynomials of $L$ and schedules their reduction with respect to $G$ as tasks. Throughout the computation, every nonzero remainder added to the basis is added to $G$ with its lineage as the key. Each such remainder also triggers the creation of S-polynomials using it and every element in $G$ and scheduling the reduction thereof as additional tasks. The process is done when there are no remaining tasks.

There is a way to track the tasks being created by turning on the option Verbose.

i5 : QQ[a..d];
i6 : f0 = a*b-c^2;
i7 : f1 = b*c-d^2;
i8 : tgb({f0,f1},2,Verbose=>true)
You turned on Verbose! You will be notified of each new S-polynomial task created and each new GB element added to the HashTable as we go.
Scheduling a task for lineage (0-1)
Scheduling task for lineage ((0-1)-0)
Scheduling task for lineage ((0-1)-1)
Adding the following remainder to GB: -c^3+a*d^2 from lineage (0-1)

                           3      2
o8 = HashTable{(0-1) => - c  + a*d }
                           2
               0 => a*b - c
                           2
               1 => b*c - d

o8 : HashTable

In the above example, the S-polynomial S(f0,f1) didn't reduce to zero hence the remainder was added to the output with key "(0-1)". The additional two S-polynomials reduced and the process ended.

Caveat

Due to threads running in parallel, it can happen that there are redundant elements in the final Groebner basis. However these can be easily removed using minimalize, for example.

See also

Ways to use tgb :

For the programmer

The object tgb is a method function with options.