The complexity of Gr\"obner computations has inspired many improvements to Buchberger's algorithm over the years. While this package does not propose an improvement to the way the algorithm operates mathematically, it offers a way to distribute the algorithm among threads that run in parallel. It is our hope that such a distributed version of the algorithm should be written in the core of the program; however, there are still important insights one can obtain from the current implementation.
To us, the most interesting is the insight into lineages (see below) of nonzero remainders that are added to the basis during a run of Buchberger. How are these affected by the structure of the input system? What do they say about the complexity of the computation itself (and not only the complexity of the basis)? These are questions at the heart of what we are aiming to discover, and the output of the threaded Gr\"obner bases method tgb returns this information in form of a lineage table.




The lineage table is a hash table, whose values are Gr\"obner basis elements, and whose keys are the lineages.
Definition. A lineage of a polynomial is a natural number, or an ordered pair of lineages, tracing its history in the given Gr\"obner basis computation.
Lineages that are natural numbers are assigned to the original input polynomials. In the example above, the 10 minors have lineages $0,\dots,9$.


If the Spolynomial of g#"i" and g#"j" produces a nonzero remainder in Buchberger's algorithm, that remainder is added to the hashtable g with key (ij), as in the following example.

As the algorithm continues, keys are concatenated, so that for example the remainder of S(0,S(1,2)) will have lineage (0,(1,2)), and so on. For more complicated lineage examples, see tgb.
Naturally, one can obtain a minimal basis or the reduced one as follows. In the output below, elements that are reduced are replaced by null, but their lineage keys are retained for informative purposes.


To get the Gr\"obner basis in standard M2 matrix format, simply call the following:

Nuts and Bolts
The main function, tgb, uses Tasks to distribute the reduction of Spolynomials using a a current version of the Groenber basis. It can reduce and minimize upon request or print out task scheduling information as it creates new tasks. The interesting part of the output may be the lineages of the basis polynomials, in addition to the Gr\"obner basis itself. Here is an example where the Gr\"obner basis is trivial.





In particular, the lineages of null values tell us what Spolynomials didn't reduce to zero until $1$ was found as a remainder.
Version 1.1 of this package was accepted for publication in volume 11 of The Journal of Software for Algebra and Geometry on 8 October 2021, in the article Threaded GrÃ¶bner bases: a Macaulay2 package. That version can be obtained from the journal or from the Macaulay2 source code repository.
This documentation describes version 1.1 of ThreadedGB.
The source code from which this documentation is derived is in the file ThreadedGB.m2.
The object ThreadedGB is a package.