Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 Ind
 Top of Book   Previous Chapter   Next Chapter 

10 General Functions
 10.1 Matrices
  10.1-1 SumIntersectionMatDestructive

  10.1-2 SolutionMat

  10.1-3 IsSameSubspace

  10.1-4 PrintDimensionsMat

  10.1-5 Example: matrices and vector spaces
 10.2 Polynomials
  10.2-1 TermsOfPolynomial

  10.2-2 IsMonomial

  10.2-3 UnivariateMonomialsOfMonomial

  10.2-4 IndeterminateAndExponentOfUnivariateMonomial

  10.2-5 IndeterminatesOfPolynomial

  10.2-6 ReduceIdeal

  10.2-7 ReducedPolynomialRingPresentation

  10.2-8 Example: monomials, polynomials and ring presentations
 10.3 Singular
  10.3-1 SingularSetNormalFormIdeal

  10.3-2 SingularPolynomialNormalForm

  10.3-3 SingularGroebnerBasis

  10.3-4 SingularReducedGroebnerBasis
 10.4 Groups
  10.4-1 HallSeniorNumber

10 General Functions

Some of the functions provided by HAPprime are not specifically aimed at homological algebra or extending the HAP package. The functions in this chapter, which are used internally by HAPprime extend some of the standard GAP functions and datatypes.

10.1 Matrices

For details of the standard GAP vector and matrix functions, see Tutorial: matrices and Reference: Matrices in the GAP tutorial and reference manuals. HAPprime provides improved versions of a couple of standard matrix operations, and two small helper functions.

10.1-1 SumIntersectionMatDestructive
> SumIntersectionMatDestructive( U, V )( operation )
> SumIntersectionMatDestructiveSE( Ubasis, Uheads, Vbasis, Vheads )( operation )

Returns a list of length 2 with, at the first position, the sum of the vector spaces generated by the rows of U and V, and, at the second position, the intersection of the spaces.

Like the GAP core function SumIntersectionMat (Reference: SumIntersectionMat), this performs Zassenhaus' algorithm to compute bases for the sum and the intersection. However, this version operates directly on the input matrices (thus corrupting them), and is rewritten to require only approximately 1.5 times the space of the original input matrices. By contrast, the original GAP version uses three times the memory of the original matrices to perform the calculation, and since it doesn't modify the input matrices will require a total of four times the space of the original matrices.

The function SumIntersectionMatDestructiveSE takes as arguments not a pair of generating matrices, but a pair of semi-echelon basis matrices and the corresponding head locations, such as is returned by a call to SemiEchelonMatDestructive (Reference: SemiEchelonMatDestructive) (these arguments must all be mutable, so SemiEchelonMat (Reference: SemiEchelonMat) cannot be used). This function is used internally by SumIntersectionMatDestructive, and is provided for the occasions when the user might already have the semi-echelon versions available, in which case a small amount of time will be saved.

10.1-2 SolutionMat
> SolutionMat( M, V )( operation )
> SolutionMatDestructive( M, V )( operation )

Calculates, for each row vector v_i in the matrix V, a solution to x_i x M = v_i, and returns these solutions in a matrix X, whose rows are the vectors x_i. If there is not a solution for a v_i, then fail is returned for that row.

These functions are identical to the kernel functions SolutionMat (Reference: SolutionMat) and SolutionMatDestructive (Reference: SolutionMatDestructive), but are provided for cases where multiple solutions using the same matrix M are required. In these cases, using this function is far faster, since the matrix is only decomposed once.

The Destructive version corrupts both the input matrices, while the non-Destructive version operates on copies of these.

10.1-3 IsSameSubspace
> IsSameSubspace( U, V )( operation )

Returns true if the subspaces spanned by the rows of U and V are the same, false otherwise.

This function treats the rows of the two matrices as vectors from the same vector space (with the same basis), and tests whether the subspace spanned by the two sets of vectors is the same.

10.1-4 PrintDimensionsMat
> PrintDimensionsMat( M )( operation )

Returns a string containing the dimensions of the matrix M in the form "mxn", where m is the number of rows and n the number of columns. If the matrix is empty, the returned string is "empty".

10.1-5 Example: matrices and vector spaces

GAP uses rows of a matrix to represent basis vectors for a vector space. In this example we have two matrics U and V that we suspect represent the same subspace. Using SolutionMat (10.1-2) we can see that V lies in U, but IsSameSubspace (10.1-3) shows that they are the same subspace, as is confirmed by having identical sums and intersections.

gap> U := [[1,2,3],[4,5,6]];;
gap> V := [[3,3,3],[5,7,9]];;
gap> SolutionMat(U, V);
[ [ -1, 1 ], [ 1, 1 ] ]
gap> IsSameSubspace(U, V);
true
gap> SumIntersectionMatDestructive(U, V);
[ [ [ 1, 2, 3 ], [ 0, 1, 2 ] ], [ [ 0, 1, 2 ], [ 1, 0, -1 ] ] ]
gap> IsSameSubspace(last[1], last[2]);
true
gap> PrintDimensionsMat(V);
"2x3"

10.2 Polynomials

GAP provides some functions for manipulating polynomials and polynomial ideals - see Reference: Polynomials and Rational Functions. The HAPprime packages adds further functions to decompose polynomials into terms and monomials, and some functions for tidying up polynomial ideals.

10.2-1 TermsOfPolynomial
> TermsOfPolynomial( poly )( attribute )

Returns: List of pairs

Returns a list of the terms in the polynomial. This list is a list of pairs of the form [mon, coeff] where mon is a monomial and coeff is the coefficient of that monomial in the polynomial. The monomials are sorted according to the total degree/lexicographic order (the same as the in MonomialGrLexOrdering (Reference: MonomialGrlexOrdering)).

10.2-2 IsMonomial
> IsMonomial( poly )( attribute )

Returns: Boolean

Returns true if poly is a monomial, i.e. the polynomial contains only one term.

10.2-3 UnivariateMonomialsOfMonomial
> UnivariateMonomialsOfMonomial( mon )( attribute )

Returns: List

Returns a list of the univariate monomials of the largest order whose product equals mon. The univariate monomials are sorted according to their indeterminate number.

10.2-4 IndeterminateAndExponentOfUnivariateMonomial
> IndeterminateAndExponentOfUnivariateMonomial( mon )( attribute )

Returns: List

Returns a list [indet, exp] where indet is the indeterminate of the univariate monomial mon and exp is the exponent of that indeterminate in the monomial. If mon is an element in the coefficient ring (i.e. the monomial contains no indeterminates) then the first element will be mon with an exponent of zero. If mon is not a univariate monomial, then fail is returned.

10.2-5 IndeterminatesOfPolynomial
> IndeterminatesOfPolynomial( poly )( attribute )

Returns: List

Returns a list of the indeterminates used in the polynomial poly.

10.2-6 ReduceIdeal
> ReduceIdeal( I, O )( operation )
> ReduceIdeal( rels, O )( operation )

Returns: Ideal or list

For an ideal I returns an ideal containing a reduced generating set for the ideal, i.e. one in which no monomial in a relation in I is divisible by the leading term of another polynomial in I. The monomial ordering to be used is specified by O (see Reference: Monomial Orderings). The ideal can instead be specified by a list of relations rels, in which case a reduced list of relations is returned.

10.2-7 ReducedPolynomialRingPresentation
> ReducedPolynomialRingPresentation( R, I[, avoid] )( operation )
> ReducedPolynomialRingPresentationMap( R, I[, avoid] )( operation )

Returns: List

For a polynomial ring R and a list of relations I in that ring, returns a list [S, J] representing a polynomial quotient ring S/J which is isomorphic to the ring R/I, but which involves the minimal number of ring indeterminates. The indeterminates in S will be distinct from thise in R, and an optional argument avoid can be used to give a list of further indeterminates to avoid when creating the ring S.

The extended version of this function, ReducedPolynomialRingPresentationMap, returns an additional third element to the list, which contains two lists giving the mapping between the new ring indeterminates and the old ring indeterminates. The first list is of polynomials in the original indeterminates, the second the equivalent polynomials in the new ring indeterminates.

10.2-8 Example: monomials, polynomials and ring presentations

A monomial is some product of ring indeterminates. A polynomial is a sum of monomials, where each monomial may also be multiplied by an element from the field of the polynomial. It can be useful to decompose polynomials as follows:

In the example below, we decompose x + xy^2 + 3y^3 into its three terms, and then further decompose the xy^2 term.

gap> R := PolynomialRing(Integers, 2);;
gap> x := R.1;; y := R.2;;
gap> poly := x + x*y^2 + 3*y^3;
x_1*x_2^2+3*x_2^3+x_1
gap> terms := TermsOfPolynomial(poly);
[ [ x_1, 1 ], [ x_2^3, 3 ], [ x_1*x_2^2, 1 ] ]
gap> UnivariateMonomialsOfMonomial(terms[3][1]);
[ x_1, x_2^2 ]
gap> IndeterminateAndExponentOfUnivariateMonomial(last[2]);
[ x_2, 2 ]

HAPprime also provides some functions to help the generation of ring presentations. In the following example we consider the polynomial ring Z[w,x,y,z] an an ideal I = < w^2 + x, w^3 + x^3 >. We first convert this ideal into reduced form (where no monomial in a polynomial is divisible by the leading term of any other polynomial). Then we calculate a reduced ring presentation for the quotient ring R/I, where we find that the indeterminate x is can be removed and a new ring S/J = Z[w,y,z]/< w^6-w^3 > is isomorphic to R/I

gap> R := PolynomialRing(Integers, 4);;
gap> w := R.1;; x := R.2;;
gap> I := [w^2 + x, w^3 + x^3];
[ x_1^2+x_2, x_1^3+x_2^3 ]
gap> ReduceIdeal(I, MonomialLexOrdering());
[ x_1^2+x_2, -x_2^3+x_1*x_2 ]
gap> 
gap> ReducedPolynomialRingPresentation(R, I);
[ Integers[x_5,x_6,x_7], [ x_5^6-x_5^3 ] ]

10.3 Singular

10.3-1 SingularSetNormalFormIdeal
> SingularSetNormalFormIdeal( I )( operation )
> SingularSetNormalFormIdealNC( I )( operation )

Returns: nothing

Sets the ideal to be used by singular for any subsequent calls to SingularPolynomialNormalForm (10.3-2) to be I. After calling this function, the singular base ring and term ordering (see SingularBaseRing (singular: SingularBaseRing) and TermOrdering (singular: TermOrdering)) will be set to be that of the ring containing I, so an additional call to SingularSetBaseRing (singular: SingularSetBaseRing) is not necessary.

The standard form of this function ensures that I is a reduced Gröbner basis with respect to the value of TermOrdering (singular: TermOrdering) for the ring containing the ideal, while the NC assumes that I is already such a Gröbner basis.

10.3-2 SingularPolynomialNormalForm
> SingularPolynomialNormalForm( poly[, I] )( operation )

Returns: Polynomial

Returns the normal form of the polynomial poly after reduction by the ideal I. The ideal can either be passed to this function, in which case it is converted to a Gröbner basis (with respect to the term ordering of the ideal's ring - see TermOrdering (singular: TermOrdering)), or the ideal to use can be set first be calling SingularSetNormalFormIdeal (10.3-1), which is more efficient for repeated use of this function (the latter function also sets the base ring and term ordering).

10.3-3 SingularGroebnerBasis
> SingularGroebnerBasis( I )( attribute )

Returns: List

Returns a list of relations which form a Gröbner basis for the ideal I given the TermOrdering (singular: TermOrdering) associated with the ring containing I. This function is the same as the singular function GroebnerBasis (singular: GroebnerBasis), but fixes a bug in that package when using unusual term ordering.

10.3-4 SingularReducedGroebnerBasis
> SingularReducedGroebnerBasis( I )( attribute )

Returns: List

Returns a list of relations which form a reduced Gröbner basis for the ideal I given the TermOrdering (singular: TermOrdering) associated with the ring containing I. This function is the equivalent of the singular function GroebnerBasis (singular: GroebnerBasis) (and uses that function), but ensures that a reduced basis is returned.

10.4 Groups

Small groups in GAP can be indexed by their small groups library number Reference: Small Groups. An alternative indexing scheme, the Hall-Senior number, is used by Jon Carlson to publish his cohomology ring calculations at http://www.math.uga.edu/~lvalero/cohointro.html. To allow comparison with these results, we provide a function that converts from the GAP small groups library numbers to Hall-Senior number for the groups of order 8, 16, 32 and 64.

10.4-1 HallSeniorNumber
> HallSeniorNumber( order, i )( attribute )
> HallSeniorNumber( G )( attribute )

Returns: Integer

Returns the Hall-Senior number for a small group (of order 8, 16, 32 or 64). The group can be specified an order, i pair from the GAP Reference: Small Groups library, or as a group G, in which case IdSmallGroup (Reference: IdSmallGroup) is used to identify the group.

gap> HallSeniorNumber(32, 5);
20
gap> HallSeniorNumber(SmallGroup(64, 1));
11
 Top of Book   Previous Chapter   Next Chapter 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 Ind

generated by GAPDoc2HTML