tgb -- threaded Gr\"obner bases

Synopsis

Usage:

tgb(List)

tgb(Ideal)
Inputs:
- L, a list, of polynomials
- I, an ideal,
Optional inputs:
- Minimal => ..., default value false, Option to specify whether the end Gr\"obner basis should be a minimal Gr\"obner basis
- Verbose => ..., default value false, Option to specify whether additional output is wanted.
Outputs:
- an instance of the type LineageTable, a hashtable whose values are a Gr\"obner basis for the ideal I or the ideal generated by L, and keys are the lineages of the corresponding elements.

Description

Threaded Gr\"obner basis uses Tasks to compute a Gr\"obner 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 : allowableThreads  = 4;

i4 : H = tgb I

                                   4 4     3 7
o4 = LineageTable{((0, 1), 2) => 9y z  - 6y z     }
                                    2 11     2 10
                  ((0, 1), 3) => 44y z   + 4y z
                                          2 6
                  ((1, 2), (0, 1)) => -43y z
                                    2 22      2 18
                  ((1, 2), 1) => 46y z   + 12y z
                                               2 4
                  ((2, 3), ((0, 1), 2)) => -47y z
                                 5 2      3 4
                  (0, 1) => - 25y z  - 19y z
                              5 3     2 4
                  (0, 2) => 5y z  + 9y z
                               5      2 4
                  (0, 3) => 28y z - 2y z
                                 4 5      3 8
                  (1, 2) => - 45y z  + 30y z
                               3 7      3 6
                  (1, 3) => 30y z  - 34y z
                              3 4     2 4
                  (2, 3) => 7y z  - 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

o4 : LineageTable

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.

i5 : H#(0,1)

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

o5 : R

Some may be curious how tgb works.

The starting basis $L$ (the input list L or L=gens I) populates the entries numbered $0$ through $n-1$ of a mutable hash table $G$, where $n$ is the length of $L$. 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.

i6 : QQ[a..d];

i7 : f0 = a*b-c^2;

i8 : f1 = b*c-d^2;

i9 : allowableThreads=2;

i10 : tgb({f0,f1},Verbose=>true)
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
o10 = LineageTable{(0, 1) => - c  + a*d }
                               2
                   0 => a*b - c
                               2
                   1 => b*c - d

o10 : LineageTable

In the example above, 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 Gr\"obner basis. However these can be easily removed using minimize, for example.

Also, allowableThreads needs to be set to an integer larger than 1, prior to calling tgb. Otherwise, errors may occur. It may be a good idea to reset allowableThreads to 1 after the threaded computations are done.

Ways to use tgb :

tgb(Ideal)
tgb(List)

For the programmer