> GP2NP( gp ) | ( function ) |
Returns: The polynomial corresponding to gp in NP form, see 2.1.
This function will convert a polynomial to the NP form.
> GP2NPList( Lgp ) | ( function ) |
Returns: The list of polynomials corresponding to Lgp in NP format.
This function will convert a list of polynomials to the NP form.
> NP2GP( np, A ) | ( function ) |
Returns: The polynomial corresponding to np in GAP form.
This function will convert an NP polynomial to a GAP polynomial in the free associative algebra A.
> NP2GPList( Lnp, A ) | ( function ) |
Returns: The list of polynomials corresponding to Lnp in GAP form.
This function will convert Lnp, a list of polynomials in NP form to a list of GAP polynomials in the free associative algebra A.
> GBNP.ConfigPrint( arg ) | ( function ) |
By default the generators of the algebra are printed as a, ..., l and everything after the twelfth generator as x. By calling this function it is possible to alter this printing convention. The argument(s) will be an algebra or arguments used for naming algebras in GAP upon creation. More specifically, we have the following options:
When the function is invoked with an algebra as argument, generators will be printed as they would be in the algebra.
When the function is invoked with a string as its argument, it is assumed that there is only 1 generator and that this should be named as indicated by the string.
When the function is invoked with an integer as its argument, generators will be printed as x.<n>, where <n> is the number of the generator.
When the function is invoked with an integer and a string as its arguments, generators will be printed as <s>.<n>, where <s> is the string given as argument and <n> the number of the generator. There is no checking whether the number given as argument is really the dimension. So it is possible that higher numbers return in the output. This way of input is useful however, because it is a distinction from the one-dimensional case and compatible with the way a free algebra is created.
When the function is invoked with a list of strings, generators will be printed with the corresponding string or x if the list is not long enough.
> PrintNP( ff ) | ( function ) |
This function prints a polynomial ff in NP format, using the letters a, b, c, ... for x_1, x_2, x_3, ..., except that everything beyond l (the 12-th letter) is printed as x.
The way generators of the algebra are printed can be changed with the function GBNP.ConfigPrint (3.2-1).
> PrintNPList( G ) | ( function ) |
This function prints a list of polynomials G in NP format, using the letters a, b, c, ... for x_1, x_2, x_3, ..., except that everything beyond l (the 12-th letter) is printed as x.
The way generators of the algebra are printed can be changed with the function GBNP.ConfigPrint (3.2-1).
> AddNP( u, v, c, d ) | ( function ) |
Returns: c*u+d*v
Computes c*u+d*v where u and v are non-commutative polynomials and c and d are scalars.
> BimulNP( u, ga, dr ) | ( function ) |
Returns: pol, the non-commutative polynomial ga*u*dr
When called with a non-commutative polynomial u and two monomials ga, dr, the function will return ga*u*dr.
> CleanNP( pol ) | ( function ) |
Returns: The cleaned up version of pol
Collects terms with same monomial, removes trivial monomials, and orders the monomials, with biggest one first.
> GtNP( u, v ) | ( function ) |
Returns: true if u > v and false if u <= v
Greater than function for NP monomials, tests whether u>v. The ordering is done by degree and then lexicographically.
> LtNP( u, v ) | ( function ) |
Returns: true if u < v and false if u >= v
Less than function for NP monomials, tests whether u<v. The ordering is done by degree and then lexicographically.
> LTermsNP( pol ) | ( function ) |
Returns: A list of leading terms
This function returns the leading terms of a list of noncommutative polynomials pol. The polynomials are nonzero and ordered in such a way that the leading monomial comes first.
> MkMonicNP( pol ) | ( function ) |
Returns: pol made monic
This function returns the scalar multiple of a non-commutative polynomial pol that is monic, i.e. has leading coefficient equal to 1.
> MulNP( u, v ) | ( function ) |
Returns: u*v
When invoked with two non-commutative polynomials u and v, this function will return the product u*v.
> Grobner( KI ) | ( function ) |
Returns: A Gröbner Basis (if found...the general problem is unsolvable)
For a list of noncommutative polynomials KI this function will use Buchberger's algorithm with normalform to find a Gröbner Basis G (if possible, the general problem is unsolvable).
> SGrobner( KI ) | ( function ) |
Returns: A Gröbner basis (if found...the general problem is unsolvable)
For a list of noncommutative polynomials KI this function will use Buchberger's algorithm with strong normalform to find a Gröbner Basis G (if possible, the general problem is unsolvable).
> BaseQA( G, t, maxno ) | ( function ) |
Returns: a list of terms forming a basis of the quotient algebra, that is, the non-commutative polynomial algebra in t variables modulo the 2-sided ideal generated by G
When called with a Gröbner basis G, the number t of generators of the algebra, and a maximum number of terms to be found maxno, BaseQA will return a (partial) base of the quotient algebra. If this function is invoked with maxno equal to 0, then a full basis will be given.
> DimQA( G, n ) | ( function ) |
Returns: The dimension of the quotient algebra
When called with a Gröbner basis G and a number of variables n, DimQA will return the dimension of the quotient algebra if it is finite. To check whether the dimension of the quotient algebra is finite and to check for the type of growth if it is infinite see also the functions FinCheck (3.6-4), DetermineGrowth (3.6-2) and DetermineGrowthObs (3.6-3) in section 3.6.
> MatricesQA( t, B, GB ) | ( function ) |
Returns: The matrix representation for the t generators of the algebra for right multiplication in the quotient algebra
Given a basis of the quotient algebra B and a Gröbner basis (record) GB, this function creates a matrix representation for the t generators of the algebra for right multiplication in the quotient algebra.
> MatricesQAC( t, B, GB ) | ( function ) |
Returns: The compressed matrix representation for the t generators of the algebra for right multiplication in the quotient algebra
Given a basis of the quotient algebra B and a Gröbner basis (record) GB, this function creates compressed matrix representations for all t generators of the algebra for right multiplication in the quotient algebra.
For this version to do better than MatrixQA, the field must be finite and of order at most 256. For more information about compression, see Reference: Row Vectors over Finite Fields.
> MatrixQA( i, B, GB ) | ( function ) |
Returns: The matrix representation for the i-th generator of the algebra for right multiplication in the quotient algebra
Given a basis of the quotient algebra B and a Gröbner basis (record) GB, this function creates a matrix representation for the i-th generator of the algebra for right multiplication.
> MatrixQAC( i, B, GB ) | ( function ) |
Returns: The compressed matrix representation for the i-th generator of the algebra for right multiplication in the quotient algebra
Given a basis of the quotient algebra B and a Gröbner basis (record) GB, this function creates a matrix representation for the i-th generator of the algebra for right multiplication in the quotient algebra.
For this version to do better than MatrixQA, the field must be finite and of order at most 256. For more information about compression, see Reference: Row Vectors over Finite Fields.
> MulQA( p1, p2, G ) | ( function ) |
Returns: The strong normal form of the product p1*p2 with respect to G
When called with two polynomials in NP form, p1 and p2, and a Gröbner basis G, this function will return the product in the quotient algebra.
> StrongNormalFormNP( f, G ) | ( function ) |
Returns: The strong normal form of a non-commutative polynomial with respect to G
When invoked with a non-commutative polynomial in NP form (see section 2.1) and a Gröbner basis G in NP form, this function will return the strong normal form (that is, a polynomial that is equal to f modulo G, every monomial of which is a multiple of no leading monomial of an element of G).
This function assumes that G is ordered (with the ordering LtNP (3.3-5)), that the polynomials in G are monic and cleaned (see MkMonicNP (3.3-7) and CleanNP (3.3-3)) and that polynomial f is clean. Note that a Gröbner basis as returned by a function like SGrobner (3.4-2) is in the required form.
This section contains some functions designed to obtain information on the dimensionality of the quotient algebra related to the Gröbner basis (the full polynomial ring modulo the two-sided ideal I generated by the Gröbner basis). All functions in this section work in the more general setting where we have a monomial ideal with a basis of which no element divides any other element.
The purpose of the functions FinCheck (3.6-4), DetermineGrowth (3.6-2), and DetermineGrowthObs (3.6-3) are all closely related. Their speed decreases in this order, while their functionality increases, as illustrated from the following table.
FinCheck (3.6-4) |
DetermineGrowth (3.6-2) |
DetermineGrowthObs (3.6-3) |
|
| finite | true |
"finite" |
0 |
| infinite (polyn., d) | false |
d or [d1,d2] |
d |
| infinite (expon.) | false |
"exponential growth" |
"exponential growth" |
The function DetermineGrowth (3.6-2) only sometimes finds the exact dimension. If this is the case, that dimension is returned. If only an interval could be found then an interval [d1,d2] in which the dimension lies is returned.
With the function Preprocess (3.6-6), 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 dimension).
> DetermineGrowth( F, n ) | ( function ) |
Returns: If the quotient algebra is infinite dimensional, then false is returned. If the growth is polynomial and the algorithm found a precise degree d of the growth polynomial, then that answer is returned. If no precise answer is found, an interval [d1,d2] will be returned in which the dimension lies. If the growth is exponential, the string "Exponential Growth" is returned.
Given leading monomials F of some Gröbner basis (these can be obtained with the function LTermsNP (3.3-6)) and the size of the alphabet n, this function checks whether the quotient algebra by the ideal generated by F is finite dimensional. In doing so it constructs a graph of normal words which helps with the computations. It also checks for exponential or polynomial growth in the infinite case.
This function allows preprocessing which can give faster results. This can be done with the function Preprocess (3.6-6).
> DetermineGrowthObs( O, n ) | ( function ) |
Returns: If the growth is finite, 0 is returned. If the growth is polynomial, the degree d will be returned. If the growth is exponential, the string "exponential growth" will be returned.
Given `obstructions' O and an alphabet size n, this function computes the growth of the quotient algebra. Note that this function is much slower than the function DetermineGrowth (3.6-2), and therefore we favor the latter. However, in the case of polynomial growth, this function returns the exact degree of polynomial growth while DetermineGrowth (3.6-2) only returns bounds.
> FinCheck( F, n ) | ( function ) |
Returns: true, if the quotient algebra is finite dimensional and false otherwise
Given leading monomials F of some Gröbner basis G (these can be obtained with the function LTermsNP (3.3-6)) and the size of the alphabet n, this function checks whether the quotient algebra by the ideal generated by G is finite dimensional.
This function allows preprocessing which can give faster results. This can be done with the function Preprocess (3.6-6).
> HilbertSeries( O, n, d ) | ( function ) |
Returns: A list of coefficients of the Hilbert series up to degree d
Given a set of `obstructions' O and the size of the alphabet n, this function computes the Hilbert series up to a given degree d. Internally, it builds (part of) the graph of standard words. This function will remove zeroes from the end of the list of coefficients.
> Preprocess( ulist, alphabetsize, nrecs ) | ( function ) |
Returns: The left-reduced list of `obstructions', obtained by applying left-reduction recursively
This preprocessing of the list ulist of monomials can be applied to the set of leading terms of a Gröbner basis before calling the functions FinCheck (3.6-4), DetermineGrowth (3.6-2), or DetermineGrowthObs (3.6-3) in order to speed up calculations using these functions. As the name suggests, alphabetsize should be the size of the alphabet. The parameter nrecs gives the maximum number of recursion steps in the preprocessing (0 means no restriction). For more information about this function see [K03].
> PrintTraceList( G ) | ( function ) |
When invoked with a set of traced non-commutative polynomials G, this function prints the traces of that list.
> PrintTracePol( pol ) | ( function ) |
This function prints the trace of a non-commutative polynomial pol.
> PrintNPListTrace( G ) | ( function ) |
When invoked with a set of traced non-commutative polynomials G, this function prints the list of the traced polynomials, without the trace.
> SGrobnerTrace( KI ) | ( function ) |
Returns: Gröbner Basis, traceable
For a list of noncommutative polynomials KI this function will use Buchberger's algorithm with strong normal form to find a Gröbner Basis G (if possible; the general problem is unsolvable).
The results will be traceable. Functions that can print the Gröbner basis are PrintTraceList (3.7-1) (with the trace) and PrintNPListTrace (3.7-3) (without the trace).
> StrongNormalFormTraceNP( f, G ) | ( function ) |
Returns: The strong normal form of f with respect to G
When invoked with a non-commutative polynomial f and a list of non-commutative polynomials G with trace information, this function computes the strong normal form of f with respect to G including trace information. The polynomial f can be either in the form of a trace record 2.5 or can be just a polynomial in NP form 2.1.
This function assumes that G is ordered (with the ordering LtNP (3.3-5)), that the polynomials in G are monic and cleaned (see MkMonicNP (3.3-7) and CleanNP (3.3-3)), and that the polynomial f is clean. Note that a Gröbner basis as returned by a function like SGrobnerTrace (3.7-4) is in the required form.
More about these functions can be found in A.4 and in A.5.
> SGrobnerTrunc( KI, deg, wtv, out ) | ( function ) |
Returns: Return value depends on out. See below for more information.
When invoked with a basis of the ideal KI, a maximum weight level for the computations deg, and a weight vector wtv (a list of nonnegative integers of length the number of variables), this function will return:
a Gröbner basis of degree <=deg
a list of monomials of degree <=deg
a list of dimensions <=deg, a list by degree, and a cumulative list
all of the above.
> MakeArgumentList( mons, dim, wtv ) | ( function ) |
Returns: A list of weights of the polynomials or false.
When invoked with a set of monomials mons, a list of dimensions of every weight dim and a weight vector wtv, this function checks if all polynomials in 'G' are homogeneous (checks if the lengths of all terms of a polynomial are equal) and returns the list of weights of the polynomials or false.
> BaseQAPTS( GBR, t, mt, maxno ) | ( function ) |
Returns: A list of terms forming a basis of the quotient algebra, the NP algebra where the relations of GBR are modded out
When called with a Gröbner basis record GBR (see 2.8), the number of algebra generators t, the number of module generators mt, and a maximum number of terms to be found, maxno, BaseQAPTS will return a (partial) base of the quotient algebra. If this function is invoked with maxno equal to 0, then a full basis will be given.
If the module is one-dimensional, it is possible to use the algebra instead. This can be done by entering 0 for the number mt of module generators
> DimQAPTS( GBR, n, mn ) | ( function ) |
Returns: The dimension of the quotient algebra
When called with a Gröbner basis record GBR (see 2.8), a number of variables n, and a number of elements mn in the module alphabet, DimQAPTS will return the dimension of the quotient algebra.
> MulQAPTS( p1, p2, GBR ) | ( function ) |
Returns: The strong normal form of the product p1*p2 with respect to GBR
When called with two polynomials in NP form, p1 and p2 and a Gröbner basis record GBR, this function will return the product p1*p2 in the quotient algebra.
> SGrobnerPTS( KI_p, KI_ts ) | ( function ) |
Returns: A record GBR containing a Gröbner basis (if found...the general problem is unsolvable). GBR.p will contain the prefix rules and GBR.ts will contain the two-sided rules
For lists of NPMs, noncommutative polynomials for modules, KI_p, and noncommutative polynomials, NPS, KI_ts, this function will use Buchberger's algorithm with strong normalform applied to the union of KI_p, KI_ts, the set of polynomials x*e-x and x*m[i] for x a standard indeterminate, a module generator m[j] or the dummy indeterminate e, and the set of all e*x -x for x a standard indeterminate, to find a Gröbner Basis record GBR (if possible; the general problem is unsolvable). This record will have a Gröbner Basis GBR.ts for the ideal generated by KI_ts and an intersection with the module GBR.p representing the module relations needed to find representative vectors in the module uniquely by means of a NormalForm computation modding out GBR.p and, for the scalars, GBR.ts.
> StrongNormalFormPTSNP( f, GBR ) | ( function ) |
Returns: The strong normal form of a non-commutative polynomial with respect to GBR
When invoked with a non-commutative polynomial in NP form (see section 2.1) and a Gröbner basis record GBR (see 2.8), this function will return the strong normal form (the polynomial reduced by the prefix and two-sided relations of the Gröbner basis combination).
This function assumes that GBR is ordered (with the ordering LtNP (3.3-5)), that the polynomials in GBR are monic and cleaned (see MkMonicNP (3.3-7) and CleanNP (3.3-3)) and that polynomial f is clean. Note that a Gröbner basis record as returned by a function like SGrobnerPTS (3.9-4) is in the required form.
generated by GAPDoc2HTML