# tgb -- threaded Groebner bases

## Synopsis

• Usage:
tgb(List, ZZ)
tgb(Ideal, ZZ)
• Inputs:
• L, a list, of polynomials
• I, an ideal,
• n, an integer, number of threads to use to compute the Groebner basis
• Optional inputs:
• Minimal => ..., default value false, Option to specify whether the end Groebner basis should be a minimal Groebner basis
• Verbose => ..., default value false, Option to specify whether additional output is wanted.
• Outputs:
• , whose values are a Groebner basis for the ideal I or the ideal generated by L, and keys are the lineages of the corresponding elements.

## 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.