A Gröbner Basis can be infinite. Even when a Gröbner Basis is finite, it can be very large and therefore difficult for a person to digest. One often finds that there are many relations which are generated which do not enhance our understanding of the mathematics. In many cases we want a basis for an ideal which is minimal (i.e., has smallest cardinality) or which is minimal as a subset of a given basis. We, therefore, find it helpful to take a list of rules which are generated by the GB algorithm and make them smaller. Consider the following example.
Example 30.1 A GB generated by the set {PTP -TP,P2 -P} is the set {PTnP -TnP : n ≥ 1}∪{P2 - P} regardless of the term order used. No smaller GB exists.
Here just two relations generate infinitely many. One way to view this example is that the computer discovers that if a subspace (represented by ran(P) in the computation) is invariant for a linear transformation T, then it is invariant for Tn for every n ≥ 1.
The GB algorithms tries to generate this infinite set of relations and at any time has generated a finite subset of them. When we are trying to discover a theorem or elegant formulas, often these relations having higher powers are irrelevant and clutter the spreadsheet which merely serves to confuse the user.
This introduces the next topic which is shrinking a set of relations to eliminate redundancy. Our desire is to take the generated basis and to remove mathematical redundancy from the generating set without destroying the information which was gained while running the GB algorithm.
We have two lines of attack on this problem. In this chapter we describe one which is embodied in the command RemoveRedundant. In Chapter 21 we describe another approach.
Our first line of attack works only when the set of relations under consideration has been generated by NCMakeGB and then only either
This approach is very fast.
If one has created a set of relations G by using NCMakeGB, then one can use history (gotten by the WhatIsHistory command — see 29.2.1 recorded during the run of NCMakeGB to find a smaller subset of G which generates the same basis. The essential idea is to take the history from the previous run of NCMakeGB and use it to construct a directed acyclic graph (DAG) representing the information. Then a fast combinatorial DAG search can be done.
Note that the WhatIsHistory command only records one way in which a certain relation is generated. For example, suppose that p5 is an S-polynomial of p1 and p2 and p5 is not reduced. It may also be the case the p5 is an S-polynomial of p3 and p4 and p5 is not reduced. If the program computed p5 by taking the S-ppolynomials of p1 and p2 first, then the fact that p5 is an S-polynomial of p3 and p4 will not be recorded.
RemoveRedundent requires a history and a list of polynomials. NCMakeGB records part of what it is doing during its computation and that can be used to determine some facts about ideal membership. This history can be though of as a directed acyclic graph (abbreviated as dag)1. The the list of polynomials is a subset V of all of the nodes and the output of RemoveRedundent is another set R of nodes v in V . Let √ denote a connected path which runs from v backward in time until it reaches a leaf. Now ends at v in the set V and may as we go backwards along it in time leave V then come back etc. Let v() denote the earliest node of in V . It belongs to R. Indeed, R = {v() for all maximal connected forward flowing paths ending in V }. For example, if some path ends in v and the node immediately before v is not in V , then v is in R. Now we give more formal statements and about how the RemoveRedundent algorithm works.
Let p1,…,pn K[x1,…,xn]. Let T be a tree on the nodes {1,…,n}. We say that the tree represents the development of p1,…,pn if it is the case that for every j = 1,…,n either
OR
Now suppose that T is a tree on {1,…,n} and it represents the development of p1,…,pn. If j is the root of the tree and k1,…,kr are the leafs of T, then pj lies in the ideal generated by pk1,…,pkr. In fact, pa lies in the ideal generated by pk1,…,pkr for every a such that both 1 ≤ a ≤ n.
Now, if a tree T represents the development of p1,…,pn and one chooses a subset {k1,…,kr}{1,…,n}, then one can consider the largest subgraph of T for which each node kℓ has no edge leading from it. Each connected component of this subgraph will be a tree. Let To be such a connected component of T and {ℓ1,…,ℓw} be the nodes of To. It is clear that the tree To represents the development of pℓ1,…,pℓw.
This is the key to the function RemoveRedundent. This function takes a tree T which represents the development of p1,…,pn and a list of nodes {ℓ1,…,ℓw}. The algorithm proceeds as follows.
Let result = {ℓ1,…,ℓw};
Let unchanged = False;
while(unchanged)
unchanged = False;
temp = result;
while(unchanged is False and temp is not the empty set)
Pick ℓ temp;
Let temp = temp\{ℓ};
More here ? MARK whats this mean
end while
end while
This shrinking is done using the commands RemoveRedundent and SmallBasis.
For example, after loading the files NCGB.m, SmallBasis3.m (§21.1.1) and RemoveRedundent.m (§30.1.2), we can execute the commands to compute a subset of a Gröbner Basis for the set of relations {p **p - p,p **a **p - a **p}:
In[2]:= SetKnowns[a,p]
In[3]:= {p**p-p,p**a**p - a**p} Out[3]= {-p + p ** p, -a ** p + p ** a ** p} In[4]:= NCMakeGB[%,4] |
Out[4]= {-p + p ** p, -a ** p + p ** a ** p, -a ** a ** p + p ** a ** a ** p,
> -a ** a ** a ** p + p ** a ** a ** a ** p, > -a ** a ** a ** a ** p + p ** a ** a ** a ** a ** p, > -a ** a ** a ** a ** a ** p + p ** a ** a ** a ** a ** a ** p, > -a ** a ** a ** a ** a ** a ** p + p ** a ** a ** a ** a ** a ** a ** p, > -a ** a ** a ** a ** a ** a ** a ** p + > p ** a ** a ** a ** a ** a ** a ** a ** p, > -a ** a ** a ** a ** a ** a ** a ** a ** p + > p ** a ** a ** a ** a ** a ** a ** a ** a ** p, > -a ** a ** a ** a ** a ** a ** a ** a ** a ** p + > p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, > -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p + > p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, > -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p + > p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, > -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p + > p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, > -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p + > p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p\ > , -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** > a ** p + p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** > a ** a ** a ** p, -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** > a ** a ** a ** a ** a ** p + > p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** > a ** a ** p, -a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** > a ** a ** a ** a ** a ** p + > p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** > a ** a ** a ** p} |
The command SmallBasis takes this (or any) set of relations and shrinks it down to a smaller set of relations which generate the same ideal. One must have a monomial order set because SmallBasis (§21.1.1) calls NCMakeGB. SmallBasis returns a subset of the original set of relations. In the example below the SmallBasis command shows that the ideal generated by the set Out[4] equals the ideal generated by {-p + p **p,-a **p + p **a **p}. 2
In[5]:= SmallBasis[%4,{},4];
Out[5]= {-p + p ** p, -a ** p + p ** a ** p} |
Unfortunately in larger examples, SmallBasis is very slow which prompts the development of a more specialized command RemoveRedundant. This can be run only after NCMakeGB has been run because it uses the history of how the GB was produced. This history is equivalent to a tree which tells what relation came from what other relations RemoveRedundant uses only tree search methods so it is faster than SmallBasis.
As one sees below the information required for RemoveRedundant is a subset of the last GB produced in your session.
Before calling RemoveRedundent, one must acquire the history of the last GB produced in your section. This takes 2 commands which we now illustrate and which we explain afterward.
In[5]:= WhatAreNumbers[]
Out[5]= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17} In[6]:= WhatIsHistory[%] |
Out[6]= {{1, p ** p -> p, {0, 0}, {}},
> {2, p ** a ** p -> a ** p, {0, 0}, {}}, > {3, p ** a ** a ** p -> a ** a ** p, {2, 2}, {2}}, > {4, p ** a ** a ** a ** p -> a ** a ** a ** p, {3, 2}, {2}}, > {5, p ** a ** a ** a ** a ** p -> a ** a ** a ** a ** p, {3, 3}, {3}}, > {6, p ** a ** a ** a ** a ** a ** p -> a ** a ** a ** a ** a ** p, > {5, 2}, {2}}, {7, p ** a ** a ** a ** a ** a ** a ** p -> > a ** a ** a ** a ** a ** a ** p, {5, 3}, {3}}, > {8, p ** a ** a ** a ** a ** a ** a ** a ** p -> > a ** a ** a ** a ** a ** a ** a ** p, {5, 4}, {4}}, > {9, p ** a ** a ** a ** a ** a ** a ** a ** a ** p -> > a ** a ** a ** a ** a ** a ** a ** a ** p, {5, 5}, {5}}, > {10, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p -> > a ** a ** a ** a ** a ** a ** a ** a ** a ** p, {9, 2}, {2}}, > {11, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p -> > a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, {9, 3}, {3}}, > {12, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p -> > a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, {9, 4}, {4}}\ > , {13, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** > p -> a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, > {9, 5}, {5}}, {14, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** > a ** a ** a ** a ** p -> > a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p, > {9, 6}, {6}}, {15, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** > a ** a ** a ** a ** a ** p -> > a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** p > , {9, 7}, {7}}, {16, p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** > a ** a ** a ** a ** a ** a ** p -> > a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** > a ** p, {9, 8}, {8}}, {17, > p ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** > a ** a ** a ** p -> > a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** a ** > a ** a ** p, {9, 9}, {9}}} |
The call to RemoveRedundent is:
In[7]:= RemoveRedundent[Out[4],Out[6]];
Out[7]= {-p + p ** p, -a ** p + p ** a ** p} |
The first command recalls the number associated to all of the relations which occurred during the previous run of Mora’s algorithm. The second command gives the ancestory and other information related to relations 1, 2, …. One could have used any list of numbers (between 1 and 17) as the argument to the WhatIsHistory command and obtained only the history of those relations.
As a second example, after loading the files NCGB.m, SmallBasis3.m and RemoveRedundent.m, we can execute the following commands to compute a Gröbner Basis for the set of relations {x2 - a,x3 - b}:
In[3]:= SetKnowns[a,b,x]
In[4]:= NCMakeGB[{x**x-a,x**x**x-b},10] Out[4]= {-a + x ** x, -b + a ** x, -b + x ** a, -a ** a + b ** x, > -a ** b + b ** a, -a ** a + x ** b, -b ** b + a ** a ** a} |
Now, one might want to find a smaller generating set for the ideal specified above. The following command does that and took 9 seconds using the C++ version of the code.
In[5]:= SmallBasis[%4,{},3]
Out[5]= {a ** x -> b, x ** x -> a} |
Alternatively, one can use the command RemoveRedundent to generate the same result in 2 seconds. There are two steps which need to be performed before calling RemoveRedundent.
In[6]:= WhatAreNumbers[]
Out[6]= {1, 2, 3, 4, 5, 6, 7} In[7]:= WhatIsHistory[%] |
Out[7]= {{1, a ** x -> b, {0, 0}, {}}, {2, x ** x -> a, {0, 0}, {}},
> {3, b ** x -> a ** a, {1, 2}, {}}, {4, x ** a -> b, {2, 2}, {1}}, > {5, x ** b -> a ** a, {4, 1}, {3}}, {6, b ** a -> a ** b, {3, 2}, {1}}, > {7, a ** a ** a -> b ** b, {3, 4}, {}}} |
The call to RemoveRedundent is:
In[8]:= RemoveRedundent[%4,Out[12]]
Out[8]= {a ** x -> b, x ** x -> a} |
Here is a session which does roughly what the spreadsheet command does. For more detail see Chapter 15
In[11]:=NCMakeGB[FAC,2];
In[11]:=SmallBasisByCategory[RemoveRedundant[%] ]; |
The next command tries to see if any of the undigested relations can be made simpler using the digested relations
In[12]:=NCSimplifyAll[%11, DigestedRelations[%11] ];
|
Finally we output the result to the file “SecondOutputForDemo”??.
In[13]:=RegularOutput[%12, "SecondOutputForDemo"];
|
Now we return to the strategy demos of Chapter 15.
Inserting the command RemoveRedundant inside of small basis may change the answer, but it yields the same answer as SmallBasis would have given with one particular order on the set of relations given as input. All this assumes that the number of iterations is large. Inserting RemoveRedundant saves much computer time.