ThreadedGB -- a package for distributed computation of Gr\"obner bases

Description

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 non-zero 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.

i1 : QQ[x_1,x_0,x_3,x_5,x_4,x_2,MonomialOrder=>Lex]

o1 = QQ[x , x , x , x , x , x ]
         1   0   3   5   4   2

o1 : PolynomialRing

i2 : rnc = minors(2, matrix{{x_0..x_4},{x_1..x_5}})

               2                                2                       
o2 = ideal (- x  + x x , - x x  + x x , x x  - x , - x x  + x x , x x  -
               1    0 2     1 2    0 3   1 3    2     1 3    0 4   1 4  
     ------------------------------------------------------------------------
              2                                                            2
     x x , - x  + x x , - x x  + x x , x x  - x x , - x x  + x x , x x  - x )
      3 2     3    4 2     1 4    0 5   1 5    4 2     3 4    5 2   3 5    4

o2 : Ideal of QQ[x , x , x , x , x , x ]
                  1   0   3   5   4   2

i3 : allowableThreads  =  4

o3 = 4

i4 : g = tgb(rnc)

                                        3
o4 = LineageTable{(1, 2) => - x x x  + x   }
                               0 4 2    2
                                          2
                  (1, 4) => - x x x  + x x
                               0 5 2    3 2
                                 2      2
                  (1, 7) => - x x  + x x
                               0 4    4 2
                                    2
                  (2, 3) => x x  - x
                             0 4    2
                  (4, 6) => x x  - x x
                             0 5    3 2
                               2      3
                  (8, 9) => - x x  + x
                               5 2    4
                          2
                  0 => - x  + x x
                          1    0 2
                  1 => - x x  + x x
                          1 2    0 3
                               2
                  2 => x x  - x
                        1 3    2
                  3 => - x x  + x x
                          1 3    0 4
                  4 => x x  - x x
                        1 4    3 2
                          2
                  5 => - x  + x x
                          3    4 2
                  6 => - x x  + x x
                          1 4    0 5
                  7 => x x  - x x
                        1 5    4 2
                  8 => - x x  + x x
                          3 4    5 2
                               2
                  9 => x x  - x
                        3 5    4

o4 : LineageTable

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

i5 : g#1

o5 = - x x  + x x
        1 2    0 3

o5 : QQ[x , x , x , x , x , x ]
         1   0   3   5   4   2

i6 : g#2

             2
o6 = x x  - x
      1 3    2

o6 : QQ[x , x , x , x , x , x ]
         1   0   3   5   4   2

If the S-polynomial of g#"i" and g#"j" produces a non-zero remainder in Buchberger's algorithm, that remainder is added to the hashtable g with key (i-j), as in the following example.

i7 : g#(1,2)

                 3
o7 = - x x x  + x
        0 4 2    2

o7 : QQ[x , x , x , x , x , x ]
         1   0   3   5   4   2

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.

i8 : minimize g

o8 = LineageTable{(1, 2) => null       }
                  (1, 4) => null
                  (1, 7) => null
                                    2
                  (2, 3) => x x  - x
                             0 4    2
                  (4, 6) => x x  - x x
                             0 5    3 2
                             2      3
                  (8, 9) => x x  - x
                             5 2    4
                        2
                  0 => x  - x x
                        1    0 2
                  1 => x x  - x x
                        1 2    0 3
                  2 => null
                  3 => x x  - x x
                        1 3    0 4
                  4 => null
                        2
                  5 => x  - x x
                        3    4 2
                  6 => x x  - x x
                        1 4    0 5
                  7 => x x  - x x
                        1 5    4 2
                  8 => x x  - x x
                        3 4    5 2
                               2
                  9 => x x  - x
                        3 5    4

o8 : LineageTable

i9 : gRed = reduce g

o9 = LineageTable{(1, 2) => null       }
                  (1, 4) => null
                  (1, 7) => null
                                    2
                  (2, 3) => x x  - x
                             0 4    2
                  (4, 6) => x x  - x x
                             0 5    3 2
                             2      3
                  (8, 9) => x x  - x
                             5 2    4
                        2
                  0 => x  - x x
                        1    0 2
                  1 => x x  - x x
                        1 2    0 3
                  2 => null
                               2
                  3 => x x  - x
                        1 3    2
                  4 => null
                        2
                  5 => x  - x x
                        3    4 2
                  6 => x x  - x x
                        1 4    3 2
                  7 => x x  - x x
                        1 5    4 2
                  8 => x x  - x x
                        3 4    5 2
                               2
                  9 => x x  - x
                        3 5    4

o9 : LineageTable

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

i10 : matrix gRed

o10 = | x_1^2-x_0x_2 x_1x_2-x_0x_3 x_1x_3-x_2^2 x_0x_5-x_3x_2 x_3^2-x_4x_2
      -----------------------------------------------------------------------
      x_1x_4-x_3x_2 x_1x_5-x_4x_2 x_3x_4-x_5x_2 x_3x_5-x_4^2 x_5^2x_2-x_4^3
      -----------------------------------------------------------------------
      x_0x_4-x_2^2 |

                                         1                                 11
o10 : Matrix (QQ[x , x , x , x , x , x ])  <-- (QQ[x , x , x , x , x , x ])
                  1   0   3   5   4   2             1   0   3   5   4   2

Nuts and Bolts

The main function, tgb, uses Tasks to distribute the reduction of S-polynomials 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.

i11 : QQ[a..d]

o11 = QQ[a..d]

o11 : PolynomialRing

i12 : I=ideal( -c^3+a^2+b*d, a*b*c-1,a*b*c)

                3    2
o12 = ideal (- c  + a  + b*d, a*b*c - 1, a*b*c)

o12 : Ideal of QQ[a..d]

i13 : allowableThreads =  2;

i14 : T = tgb(I,Verbose=>true)
Scheduling a task for lineage (0,1)
Scheduling a task for lineage (0,2)
Scheduling a task for lineage (1,2)
Scheduling task for lineage ((0,1),0)
Scheduling task for lineage ((0,1),1)
Scheduling task for lineage ((0,1),2)
Adding the following remainder to GB: Scheduling task for lineage ((0,2),0)
Scheduling task for lineage ((0,2),1)
Scheduling task for lineage ((0,2),(0,1))
Scheduling task for lineage ((0,2),2)
Adding the following remainder to GB: -a^3*b-a*b^2*d+c^2 from lineage (0,1)
Adding the following remainder to GB: -1 from lineage (1,2)
-a^3*b-a*b^2*d from lineage (0,2)
Found a unit in the Groebner basis; reducing now.

o14 = LineageTable{(0, 1) => null}
                   (0, 2) => null
                   (1, 2) => 1
                   0 => null
                   1 => null
                   2 => null

o14 : LineageTable

i15 : allowableThreads = 1;

In particular, the lineages of null values tell us what S-polynomials didn't reduce to zero until $1$ was found as a remainder.

Authors

Certification

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.

Version

This documentation describes version 1.1 of ThreadedGB.

Source code

The source code from which this documentation is derived is in the file ThreadedGB.m2.

Exports

Types
- LineageTable -- a hash table of Gr\"obner basis polynomials and their lineages
Functions and commands
- minimize -- turn a Gr\"obner basis computed using threaded Gr\"obner bases into a minimal one
- reduce -- produce a reduced Gr\"obner basis from one computed by threaded Gr\"obner bases
- tgb -- threaded Gr\"obner bases
Methods
- matrix(LineageTable) -- extract a matrix of polynomials from values of a LineageTable after deleting null values
- minimize(LineageTable) -- see minimize -- turn a Gr\"obner basis computed using threaded Gr\"obner bases into a minimal one
- reduce(LineageTable) -- see reduce -- produce a reduced Gr\"obner basis from one computed by threaded Gr\"obner bases
- tgb(Ideal) -- see tgb -- threaded Gr\"obner bases
- tgb(List) -- see tgb -- threaded Gr\"obner bases
Symbols
- Minimal -- Option to specify whether the end Gr\"obner basis should be a minimal Gr\"obner basis

For the programmer

The object ThreadedGB is a package.