The complexity of Groebner 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 Groebner 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 : g = tgb(rnc,4)
3
o3 = HashTable{(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
o3 : HashTable
|
The lineage table is a hash table, whose values are Groebner basis elements, and whose kesy are the lineages.
Definition. A Lineage of a polynomial is a string tracing its history in the given Groebner basis computation.
Lineages of length 1-- in the example above 0,…,9-- are the original input polynomials. In the example above, these are the 10 minors.
i4 : g#"1"
o4 = - x x + x x
1 2 0 3
o4 : QQ[x , x , x , x , x , x ]
1 0 3 5 4 2
|
i5 : g#"2"
2
o5 = x x - x
1 3 2
o5 : 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.
i6 : g#"(1-2)"
3
o6 = - x x x + x
0 4 2 2
o6 : 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.
i7 : minimalize g
o7 = HashTable{(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
o7 : HashTable
|
i8 : gRed = reduce g
o8 = HashTable{(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
o8 : HashTable
|
To get the Groebner basis in stanard M2 matrix format, use cleanUp:
i9 : cleanUp gRed
o9 = | x_5^2x_2-x_4^3 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_0x_4-x_2^2 |
1 11
o9 : 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 minimalize upon request, or print out task scheduling information as it creates new tasks. The interesting part of the output may be the actual lineages of the basis polynomials, in addition to the Groebner basis itself. Here is a verbose example when the Groebner basis is trivial.
i10 : QQ[a..d] o10 = QQ[a, b, c, d] o10 : PolynomialRing |
i11 : I=ideal( -c^3+a^2+b*d, a*b*c-1,a*b*c)
3 2
o11 = ideal (- c + a + b*d, a*b*c - 1, a*b*c)
o11 : Ideal of QQ[a, b, c, d]
|
i12 : T = tgb(I,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)
Scheduling task for lineage ((0-1)-2)
Adding the following remainder to GB: -a^3*b-a*b^2*d+c^2 from lineage (0-1)
Scheduling task for lineage (((0-1)-2)-0)
Scheduling task for lineage (((0-1)-2)-1)
Scheduling task for lineage (((0-1)-2)-2)
Scheduling task for lineage (((0-1)-2)-(0-1))
Adding the following remainder to GB: -a^2 from lineage ((0-1)-2)
Scheduling task for lineage ((((0-1)-2)-1)-0)
Scheduling task for lineage ((((0-1)-2)-1)-1)
Scheduling task for lineage ((((0-1)-2)-1)-2)
Scheduling task for lineage ((((0-1)-2)-1)-(0-1))
Scheduling task for lineage ((((0-1)-2)-1)-((0-1)-2))
Adding the following remainder to GB: a from lineage (((0-1)-2)-1)
Scheduling task for lineage ((((0-1)-2)-(0-1))-0)
Scheduling task for lineage ((((0-1)-2)-(0-1))-1)
Scheduling task for lineage ((((0-1)-2)-(0-1))-2)
Scheduling task for lineage ((((0-1)-2)-(0-1))-(0-1))
Scheduling task for lineage ((((0-1)-2)-(0-1))-(((0-1)-2)-1))
Scheduling task for lineage ((((0-1)-2)-(0-1))-((0-1)-2))
Adding the following remainder to GB: c^2 from lineage (((0-1)-2)-(0-1))
Adding the following remainder to GB: 1 from lineage ((((0-1)-2)-1)-1)
Scheduling a task for lineage (0-2)
Scheduling a task for lineage (1-2)
Found 1 or -1 in the Groebner basis; reducing now.
o12 = HashTable{((((0-1)-2)-1)-1) => 1 }
(((0-1)-2)-(0-1)) => null
(((0-1)-2)-1) => null
((0-1)-2) => null
(0-1) => null
0 => null
1 => null
2 => null
o12 : HashTable
|
In particular, the lineages of null values tell us what S-polynomials didn’t reduce to zero until 1 was found as a remainder.
This documentation describes version 1.0 of ThreadedGB.
The source code from which this documentation is derived is in the file ThreadedGB.m2.