The main datatype of the GBNP package is a list of non-commutative polynomials (NPs). The data type for a non-commutative polynomial, referred to as its NP format, is a list of two lists:
The first list is a list m of monomials.
The second list is a list c of coefficients of these monomials.
The two lists have the same length. The polynomial represented by the ordered pair [m,c] is \(\sum_i c_i m_i\).
A monomial is a list of positive integers. They are interpreted as the indices of the variables. So, if k = [1,2,3,2,1] and the variables are \(x\),\(y\),\(z\) (in this order), then k represents the monomial \(xyzyx\). By the way, the name of the variables has no meaning. There are various ways to print these but the default is \(a\),\(b\),\(c\),\(\ldots\) (see below).
The zero polynomial is represented by [[],[]]. The polynomial 1 is represented by [[[]],[1]].
The algorithms work for the algebra \(\mathbb F\langle\langle x_1,x_2,\ldots,x_t\rangle\rangle\) of non-commutative polynomials in t variables over the field \(\mathbb F\). Accordingly, the list c should contain elements of \(\mathbb F\). It is not always easy to recover \(\mathbb F\) from the list c. The GAP functions One and Zero can be of some help.
In order to facilitate viewing the polynomials, we provide the function PrintNP (3.2-1). For instance
PrintNP([[[1,2],[2,1]],[3,-1]]);
yields
3ab - ba
Indeed, we have the names: a, b, c, \(\ldots\) for \(x_1\), \(x_2\), \(x_3\), \(\ldots\), except that everything beyond \(l\) (the 12-th letter) is called \(x\). This can be easily changed by calling the function GBNP.ConfigPrint, which can be found in Section 3.2.
The function PrintNPList (3.2-3) is available for printing a list of NPs (=non-commutative polynomials).
In order to facilitate testing whether two data structures represent the same NP, we use the convention that polynomials are clean
. This means that they look as if they are output of the function CleanNP (3.3-7). In other words:
each monomial occurs at most once in the list of monomials,
no monomials occur whose coefficients are zero,
the monomials are ordered (total degree first, then lexicographically) from big to small.
An advantage of the ordering is that the leading monomial of an NP p is just p[1][1] and that its leading coefficient is p[2][1]. Users who want to work with other orderings can use the functions defined in the NMO extension [Con10] to GBNP.
In Section 2.1 the NP format for elements of a free algebra \(A\) of non-commutative polynomials in a fixed number of variables is described. This format can be adjusted slightly to allow the use of a free right module \(A^n\) of finite rank \(n\) over \(A\). The internal format of an element of the module is similar to that of a non-commutative polynomial. The only change is that each monomial will start with a negative number. The absolute value of this number is the index of the standard basis vector of the free module.
For example in the free \(\mathbb F\langle\langle x_1, x_2,\ldots, x_t\rangle\rangle\)-module of rank 3, the expression [[[-1]],[1]] represents \([1,0,0]\) and [[[-1,1,2],[-1,2,1],[-3,2,2,2]],[6,-7,9]] represents \([6x_1x_2-7x_2x_1,0,9x_2^3]\). The zero vector is the represented in the same way as its NP format counterpart in 2.1 and the only one without a negative entry: [[],[]]. We refer to this format as the NPM format.
Elements of modules are printed as vectors. See Section 3.9 on how to use modules. Examples A.19, A.21, and A.20 are also recommended.
The core function is SGrobner (3.4-2) (which is short for Strong Gröbner, as we use the Strong Normal Form, discussed in Section StrongNormalFormNPM (3.9-5), most of the time). It takes a list of NPs in a free algebra \(A\) and prepares two lists for treatment in a loop:
First the list itself, called G. Before entering the loop, G is cleaned, ordered, and its elements are made monic, that is, multiplied by a scalar so that the leading coefficient becomes one. The ordering is done by comparison of leading monomials. The ordering on leading monomials is length lexicographic. For other orderings, the functions of the NMO extension can be used; see [Con10].
Second the list of all normal forms with respect to G of S-polynomials of elements of G. This list is called D. For a Gröbner basis, the S-polynomials of polynomials in D (possibly with an element of G) need to be computed. If D is empty then G is a Gröbner basis.
Then, the function calls the routine GBNP.SGrobnerLoop on the arguments G, D which are changed in an attempt to modify G while still preserving the following two properties.
G generates the same two-sided ideal \(I\) in \(A\) as before.
D contains all normal forms with respect to G of S-polynomials of elements from G that need to reduce to zero for the basis to be a Gröbner basis.
The importance of this feature is that, in case of huge computations, the user may store G and D at almost any time and resume the computation by reloading G and D and calling the loop function GBNP.SGrobnerLoop whenever convenient. The only technical detail to handle is that the last element of the list G should be copied into the D list. The loop itself performs a step towards making G more like a Gröbner basis of \(I\). As in the commutative case, the progress can be indicated by use of an ordering on the set of leading monomials of the elements of G.
In contrast to the commutative case, however, this ordering is not well founded, and there is no a priori guarantee that the loop will be exited after a finite number of iterations. The loop ends when the list D is empty, in which case the work is essentially done: after some internal cleaning and a bit of further rewriting, the computation is over.
There is also a Grobner (3.4-1) function. It uses (at some places) the Normal Form instead of the Strong Normal Form algorithm. In most of our applications, this usually led to slower performance, so we are not very keen to use it.
In many of our own applications, the full polynomial ring modulo the two-sided ideal \(I\) generated by G is a finite-dimensional quotient algebra. In such cases, one would like to know the dimension (whence the function DimQA (3.5-2), QA for Quotient Algebra), find a basis (whence the function BaseQA (3.5-1)), or just the monomials up to a certain degree that are not divisible by a leading term of G (whence the function GBNP.NondivMons). Actually by use of MulQA (3.5-5), you can even multiply elements of the quotient algebra. In case it is unknown whether the quotient algebra is finite or infinite, one can use the functions FinCheckQA (3.6-2) and DetermineGrowthQA (3.6-1). When the quotient algebra is infinite dimensional you may want to determine its partial Hilbert Series. This can be done with the function HilbertSeriesQA (3.6-3).
Rather than storing all obstructions, the Gröbner basis algorithm computes the (Strong) Normal Form of obstructions from G and puts them into D whenever nonzero. At the beginning of the loop, we take the first element of the D list and prepare it for addition to G. We are then concerned with two goals:
to restore the invariant properties,
to clean up G (that is, reduce it to a more succinct, shorter set).
This is mainly done by means of additional S-polynomial and Normal Form computations.
As for data management, we have chosen to work with lists in situ, that is, not to copy the list but rather perform all operations on one and the same list. To this end we use operations like RemoveElmList and Add, see Reference: Add. The idea here is to economize on space for large computations. We do not use in situ operations everywhere, but have concentrated on the potentially biggest lists: G and D.
For checking whether a monomial can be reduced, an internal tree structure is used.
When computing with small examples, it may be handy to provide the elements of the Gröbner basis with a way of expressing them as elements in I, that is, as combinations of elements of the input. This can be done, not only for elements of G, but for any element, by the functions in the file trace.g. This file calls the file nparith.g for arithmetic keeping track of the expressions of polynomials as combinations of elements from the original basis. With respect to a given input basis B, a polynomial p in the traced version is a record, called the traced polynomial, with two fields. One field, denoted p.pol, is the usual polynomial in NP format. The other, denoted p.trace, is a list of elements indexed by B. Each element of p.trace is a list whose elements are four-tuples [ml,i,mr,c] where ml and mr are monomials, i is an index of an element of B and c is a scalar. The interpretation of this data structure is that p.pol can be written as the sum over all four-tuples [ml,i,mr,c] of \(c*ml*B_i*mr\). Functions for printing these expressions in a human understandable way are described in Section 3.7.
For computations with large and/or infinite examples, it may be convenient to truncate everything above a certain degree. In fact, we encountered various examples where the polynomials are (weighted) homogeneous and then it makes perfect sense to truncate the polynomials, that is, to disregard everything above a certain degree. For then the Grobner basis, if it exists, will be also be homogeneous and the part consisting of all of its polynomials of degree less than a given degree \(d\) is equal to the Grobner basis of the join of the original list of polynomials with all monomials of degree \(d+1\). Here an NP polynomial in \(n\) variables is called homogeneous of degree \(d\) with respect to \(v\), a vector with non-negative integers of length \(n\), if, for each of its monomials \([t_1,...,t_k]\), the sum over all \(v_{t_i}\) is equal to \(d\). The most classical choice for \(v\) is the all-one vector in which case one often speaks of homogeneous without mentioning the all-one vector. If two polynomials are homogeneous with respect to \(v\), then so are their S-polynomials. If \(K\) is a list of homogeneous polynomials with respect to \(v\), then the normal form with respect to \(K\) of any homogeneous polynomial of degree \(d\) with respect to \(v\) is again homogeneous of degree \(d\) with respect to \(v\). In particular, the Gröbner basis of a list of polynomials that are homogeneous with respect to \(v\), consists of homogeneous polynomials, and those input polynomials contributing to polynomials in the Gröbner basis of degree at most \(d\) have degree at most \(d\) themselves. These facts enable the computation of the truncated Gröbner basis. The functions of this variant can be found in Section 3.8.
Suppose we are given a finite set \(G\) of polynomials in a free non-commutative algebra \(A\) generated by, say \(t\) indeterminates, and a positive integer \(s\). Denote by \(I\) the two-sided ideal of \(A\) generated by \(G\). We can work with the free right \(A/I\) module \((A/I)^s\). See Section 2.2 on how to represent vectors of \((A/I)^s\) by elements of the free module \(A^s\). Given a subset \(W\) of \(A^s\), whose elements are called prefix relations, let \(W'\) be the submodule generated by the image of \(W\) in \((A/I)^s\). The function SGrobnerModule (3.9-1) is meant to determine the quotient module \((A/I)^s/W'\). If the algorithm terminates, it delivers a Gröbner basis for \(I\) as well as a suitable set of generators for \(W'\), with Gröbner like properties. This implies that StrongNormalFormNPM (3.9-5), a strong normal form computation, can be used to find the canonical representative in \(A^s\) of an element in \((A/I)^s/W'\). Theoretic details can be found in [Coh07]. If \((A/I)^s/W'\) is a finite-dimensional vector space over the coefficient field of \(A\), then a basis can be found by use of BaseQM (3.9-2) and its dimension can be computed by use of DimQM (3.9-3).
The function SGrobnerModule (3.9-1) calculates a Gröbner basis consisting of some two-sided relations in the algebra and some prefix or module relations in the vector space. These are returned in a record GBR. The two-sided relations can be found under the name GBR.ts and the prefix relations under the name GBR.p. Some other information is stored in this record as well.
The prefix conditions are in NPM format (see 2.2) and the two-sided relations are in NP format.
Once a Gröbner basis of a list \(G\) of polynomials in NP format, defining elements of a free algebra \(A\), is computed, the quotient algebra \(QA\) of \(A\) by the two-sided ideal generated by \(G\) (or, which amounts to the same, the Gröbner basis) can be analyzed. A number of functions are available to determine whether \(QA\) is finite dimensional or not.
Elements of \(QA\) are represented by elements of \(A\). Two elements are equal if and only if their strong normal forms coincide; see StrongNormalFormNP (3.5-6). The multiplication is take care of by MulQA (3.5-5), which is little more than the strong normal form of the product of two polynomials in NP format representing elements of \(QA\).
If \(QA\) is finite dimensional, a basis of it over the field can be found by BaseQA (3.5-1). The size of the base, in other words, the dimension of \(QA\), can be computed with DimQA (3.5-2). Right multiplication by an element of \(QA\) is a linear transformation. The matrix of this linear transformation with respect to the base, in case the element belongs to the base, can be computed by MatrixQA (3.5-3) or, for all basis elements, MatricesQA (3.5-4).
A list of leading terms of the Gröbner basis \(G\) can be constructed with LMonsNP (3.3-10). The dimension of \(QA\) only depends on this list and is computationally easier to work with than \(G\). Most functions designed to analyze dimensionality work with a monomial ideal generated by a strong Gröbner basis, which in this case means that no element divides any other element.
The function FinCheckQA (3.6-2) determines whether \(QA\) is finite or infinite dimensional. More generally, the growth of \(QA\) can be determined by means of the function DetermineGrowthQA (3.6-1), which either returns the information that \(QA\) is finite dimensional, or that \(QA\) has polynomial growth, in which case it gives bounds for the degree of polynomial growth, or that \(QA\) has exponential growth. Finally, with the function HilbertSeriesQA (3.6-3) one can compute coefficients of the Hilbert series.
The purpose of the functions FinCheckQA (3.6-2) and DetermineGrowthQA (3.6-1) are closely related. The former is faster, while the latter provides more information, as illustrated from the following table.
FinCheckQA |
DetermineGrowthQA |
|
| finite | true |
0 |
| polynomial growth | false |
d or [d1,d2] |
| exponential growth | false |
"exponential growth" |
The function DetermineGrowthQA (3.6-1) may find the exact degree of polynomial growth (if at hand). If this is the case, that degree is returned. It may also happen that only an interval [d1,d2] is returned in which the dimension lies. To force an exact answer, its third argument should be true.
With the function PreprocessAnalysisQA (3.6-4), the computations done by these 3 functions can be sped up. Note however that by applying preprocessing of the data, the set of monomials in the ideal basis is changed and corresponds no longer to the same quotient algebra (but to a quotient algebra with the same growth).
generated by GAPDoc2HTML