Documentation on the Grobner Package for Gap 4 ============================================== Authors: ======== A.M. Cohen & D.A.H. Gijsbers Address: ======= RIACA, Dept. Math. and Comp. Sc., TU/e, POB 513, 5600 MB Eindhoven, the Netherlands email A.M.Cohen@tue.nl D.A.H.Gijsbers@tue.nl Date: ===== September 24, 2001 Version: ======== 0.8.2 Downloadable: ============= at http://www.win.tue.nl/~amc/pub/grobner/GBNP0.8.2.tgz Acknowledgments: ================ -based on an earlier version by Rosane Ushirobira -based on literature by Teo Mora Summary: ======== We provide algorithms, written in the Gap 4 programming language, for computing Grobner bases of noncommutative polynomials with coefficients from a field implemented in Gap and with respect to the "total degree first then lexicographical" ordering. We further provide some variations, such as a weighted and truncated version and a tracing facility. The word "algorithm" is to be interpreted loosely here: in general one cannot expect such an algorithm to terminate, as it would imply solvability of the word problem for finitely presented (semi)groups. License+Disclaimer: =================== You are free to use the software and the source code as you please. We do not accept responsibilities for the consequences, but do request that you quote us if you publish about positive results obtained using it. For the time being the address at which you can fetch the code is at http://www.win.tue.nl/~amc/pub/software.html. Files: ====== -- nparith.g NP (= Noncommutative Polynomial) arithmetic -- nparith2.g additional NP (= Noncommutative Polynomial) arithmetic for the trace version -- printing.g algorithms for printing the NPs -- printing2.g algorithms for printing the NPs expressed as linear combinations of the original basis, for the trace version of the program. -- grobner.g Grobner basis computation and quotient algebra multiplication -- trace.g Version with tracing of Grobner basis computation -- trunc.g Truncated version of Grobner basis computation -- example?.g (?=01,...09,10,11,12) files with examples, good for testing. Description: ============ The input is a list of noncommutative polynomials (NPs). The data type for a noncommutative polynomial 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 list [m,c] of the two lists m and 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 m = [1,2,3,2,1] and the variables are x,y,z (in this order), then m stands for the monomial xyzyx. By the way, the name of the variables has no meaning. They are printed as a,b,c,... (see below). The zero polynomial is represented by [[],[]]. The polynomial 1 is represented by [[[]],[1]]. The algorithms work for the ring K of noncommutative polynomials in t variables with coefficients from a field K. In order to facilitate viewing the polynomials, we provide the function PrintNP. For instance PrintNP([[[1,2],[2,1]],[3,-1]]); yields 3ab - ba Indeed, we have the names: a, b, c, ... for x_1, x_2, x_3, .... except that everything beyond l (the 12-th letter) is called x. This can be easily changed by adapting the function TransLetter, which can be found in the file printing.g. The function PrintNPList is available for printing a list of NPs (=noncommutative polynomials). In order to facilitate testing whether two data structures represent the same NP, we use the convention that polynomials are "cleaned". This means that they look as if they are output of the function CleanNP, that is, --each monomial occurs at most once in the list of monomials, --no monomials occur whose coefficients are zero, and --the monomials are ordered (total degree first, then lexicographically) from big to small. Thus, the leading monomial of 3ab-ba is ba, and accordingly, PrintNP(CleanNP([[[1,2],[2,1]],[3,-1]])); yields - ba + 3ab 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]. The core function is SGrobner (for Strong Grobner, as we use the Strong Normal Form all the time). It takes a list B of NPs and, prepares two lists for a loopy treatment: -- first the list B itself, copied into G. Before entering the loop, G is is cleaned, ordered and its elements are made monic, that is, multiplied by a scalar so that the leading coefficient is one. -- second the list of all NormalForms wrt G of Spolynomials of elements of G that need to reduce to zero for the basis to be a Grobner basis. This list is called todo, reminding us that we still need to compute the S polynomials of these NPs (possibly with an element of G). Then, the function calls the routine SGrobnerLoop on the arguments G, todo, which are changed in an attempt to modify the arguments G and todo so that (*) G generates the same two-sided ideal I as before. (**) todo contains all NormalForms wrt G of Spolynomials of elements from G that need to reduce to zero for the basis to be a Grobner basis. The importance of this feature is that, in case of huge computations, the user may store G and todo at almost any time and take up the computation by loading G and todo and using the SGrobnerLoop whenever convenient. Now the loop ends when the list todo is empty. As we referred to above, this may never happen. But if it does, then the work is essentially done. After some internal cleaning and a bit of further rewriting, the computation is over. There is also a Grobner 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 we often have finite-dimensional quotient algebras K/I, the full noncommutative polynomial ring K modulo the two-sided ideal I generated by G. In such cases, one would like to know the dimension (whence the function dimQA, QA for Quotient Algebra), find a basis (whence the function BaseQA), or just the monomials up to a certain degree that are not divisible by a leading term of G (whence the function StandardMons). Actually by use of MulQA, you can even multiply elements of the quotient algebra. When computing with small examples, it may be useful to have the elements of the Grobner basis expressed as elements in I, that is, as combinations of elements of the input B. 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 nparith2.g for arithmetic keeping track of the expressions of polynomials as combinations of elements from the original basis. With respect to an given input basis B, a polynomial p in the traced version is a record with two fields. One field, called p.pol, is the usual NP. The other, called 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 the index of an element of B and c is a scalar (an element of K). 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 in printing2.g When computing with large and/or infinite examples, it may be handy to truncate everything above a certain degree. In fact, we encountered various examples where the polynomials are homogeneous and then it makes perfect sense to truncate the polynomials, that is, to disregard everything above a certain level of homogeneity, as the Spolynomials of lower degree can all still be handled. The routines for this case are in the file trunc.g. It is designed so that, for a given natural number k, you can recover up to degree k from the output the grobner basis, a list of standard monomials, and/or a list of dimensions of the homogeneous parts of the quotient algebra. A few words about the algorithm. Rather than storing all obstructions, it computes the (Strong) Normal Form of obstructions and puts them into todo whenever nonzero. At the beginning of the loop, we take the first element of the todo list and "try to add it" to G. We are then concerned with two goals: to restore the invariant properties (*) to (**) and to clean up G (that is, reduce it to a more succinct, shorter set). This is mainly done by means of additional Spolynomial and Normal Form computations. Finally, a comment on data management. We have used the facility to work with lists in situ, that is, not to copy the list but rather do all operations on one and the same list (by use of operations like RemoveElmList and Add). The idea here is to economize on space for large computations. We did not go all the way, but concentrated on the potentially biggest lists, like G and todo. References: =========== Edward L. Green, Noncommutative Grobner bases, and projective resolutions, pp. 29-60 in "Computational Methods for Representations of groups and algebras (Essen 1997), Birkhauser, Basel 1999. Teo Mora, An introduction to commutative and noncommutative Groebner bases, Theoretical Computer Science 134 (1994) 134-173.