5.3-1 \+
5.3-2 \-
5.3-5 \*
5.3-6 \*
5.3-7 \^
5.3-8 \*
A compressed matrix (a cmat) behaves very much like a list of cvecs. However, it insists on having only cvecs of the same length and over the same base field as its elements, and it insists on being a list without holes. Apart from these restrictions, you can use all the standard list operations with cmats (see Section 5.2.
In the rest of this chapter, we document all methods for matrices for the sake of completeness. If they behave exactly as is to be expected by the already defined operation no further explanation is given.
The basic operation to create new cmats is CMat, for which a variety of methods is available:
‣ CMat( l, cl, dochecks ) | ( method ) |
‣ CMat( l, cl ) | ( method ) |
Returns: a new cmat
A new cmat is created with rows being in the cvecclass cl. All elements of the list l must be cvecs in that class. The boolean flag dochecks indicates, whether this should be checked or not. If the flag is omitted, checks are performed. Note that l may be the empty list.
‣ CMat( l, dochecks ) | ( method ) |
‣ CMat( l ) | ( method ) |
Returns: a new cmat
A new cmat is created with rows being in the cvecclass of the vectors in l. All elements of the list l must be cvecs in the same class. The boolean flag dochecks indicates, whether this should be checked or not. If the flag is omitted, checks are performed. Note that l may not be the empty list.
‣ CMat( l, v ) | ( method ) |
Returns: a new cmat
A new cmat is created with rows being in the cvecclass of the cvec v. All elements of the list l must be cvecs in the that same class. This is checked. Note that l may be the empty list.
‣ CMat( m ) | ( method ) |
Returns: a new cmat
Creates a new cmat which is equal to m, which must be a compressed matrix in the filter IsGF2MatrixRep or the filter Is8BitMatrixRep.
There are some methods to create cmats of special form:
‣ CVEC_ZeroMat( rows, cl ) | ( function ) |
‣ CVEC_ZeroMat( rows, cols, p, d ) | ( function ) |
Returns: a new cmat
Creates a zero matrix with rows rows and cols columns over the field GF(p,d). If a cvecclass cl is given, the number of columns and the field follow from that.
‣ CVEC_IdentityMat( cl ) | ( function ) |
‣ CVEC_IdentityMat( n, p, d ) | ( function ) |
Returns: a new cmat
Creates an identity matrix with n rows and columns over the field GF(p,d). If a cvecclass cl is given, the number of columns and the field follow from that.
‣ CVEC_RandomMat( rows, cl ) | ( function ) |
‣ CVEC_RandomMat( rows, cols, p, d ) | ( function ) |
Returns: a new cmat
Creates a random matrix with rows rows and cols columns over the field GF(p,d). If a cvecclass cl is given, the number of columns and the field follow from that. Note that this is not particularly efficient.
‣ MutableCopyMat( m ) | ( method ) |
Returns: a mutable copy of m
Creates a mutable copy of the cmat m.
‣ Matrix( vectorlist, vector ) | ( method ) |
‣ MatrixNC( vectorlist, vector ) | ( method ) |
Returns: a new mutable cmat
Returns a new cmat containing the vectors in vectorlist as rows. The elements in vectorlist must be vectors of the same length as the sample vector vector and must live over the same base field. The sample vector is always necessary to be able to use the method selection. The vectorlist may be empty. The NC method does not check the inputs.
In this section, arguments named m and n are cmats and v and w are cvecs that fit into the corresponding matrices. pos is an integer between \(1\) and Length(m) if it applies to the matrix m.
‣ Add( m, v[, pos] ) | ( method ) |
Returns: nothing
Behaves exactly as expected. Note that one can only add cvecs of the right length and over the right field.
‣ Remove( m[, pos] ) | ( method ) |
Returns: a cvec
Behaves exactly as expected. No holes can be made.
‣ ELM_LIST( m, pos ) | ( method ) |
Returns: a cvec
Behaves exactly as expected. Note that this method is triggered when one uses the (reading) syntax
.m[pos]
‣ ASS_LIST( m, pos, v ) | ( method ) |
Returns: nothing
Behaves exactly as expected. Note that one can only assign to positions such that the resulting matrix has no holes. This method is triggered when one uses the (assignment) syntax
.m[pos] :=
‣ ELMS_LIST( m, poss ) | ( method ) |
Returns: a sub cmat
Behaves exactly as expected: A new matrix containing a subset of the rows is returned. Note that the row vectors are the same GAP objects as the corresponding rows of m. This operation is triggered by the expression m{poss}.
‣ ASSS_LIST( m, poss, vals ) | ( method ) |
Returns: nothing
Behaves exactly as expected. Of course all values in vals must be cvecs over the correct field and the cmat m must be a dense list afterwards. This operation is triggered by the statement m{poss} := vals.
‣ Length( m ) | ( method ) |
Returns: the number of rows of the cmat m
Behaves exactly as expected.
‣ ShallowCopy( m ) | ( method ) |
Returns: a new matrix containing the same rows than the cmat m
Behaves exactly as expected. Note that the rows of the result are the very same GAP objects than the rows of the cmat m.
‣ Collected( m ) | ( method ) |
Returns: the same as the collected list of the rows of m
Behaves exactly as expected. Just uses the standard Collected (Reference: Collected) on the list of rows.
‣ DuplicateFreeList( m ) | ( method ) |
Returns: a new mutable cmat containing the rows of m with duplicates removed
Behaves exactly as expected. Just uses the standard DuplicateFreeList (Reference: DuplicateFreeList) on the list of rows.
‣ Append( m, n ) | ( method ) |
Returns: nothing
Behaves exactly as expected. Of course, the cmats m and n must be over the same field and have the same number of columns. Note that the rows of n themselves (and no copies) will be put into the matrix m.
‣ Filtered( m, f ) | ( method ) |
Returns: a new cmat containing some of the rows of m
Behaves exactly as expected. The function f will be called for each row of m.
‣ Unbind( m, f ) | ( method ) |
Returns: nothing
Behaves exactly as expected. Of course, only the last bound row may be unbound.
Of course, the standard arithmetic infix operations \(+\), \(-\) and \(*\) (for vectors and scalars) work as expected by using the methods below. The comments on the usage of scalars in arithmetic operations involving vectors from Subsection 4.2-1 apply analogously.
5.3-1 \+‣ \+( m, n ) | ( method ) |
Returns: the sum \(\textit{m}+\textit{n}\) as a new cmat
For two cmats m and n. Works as expected.
5.3-2 \-‣ \-( m, n ) | ( method ) |
Returns: the difference \(\textit{m}-\textit{n}\) as a new cmat
For two cmats m and n. Works as expected.
‣ AdditiveInverseSameMutability( m ) | ( method ) |
‣ \-( m ) | ( method ) |
Returns: the additive inverse of m as a new cmat
For a cmat m. Works as expected.
‣ AdditiveInverseMutable( m ) | ( method ) |
Returns: the additive inverse of m as a new mutable cmat
For a cmat m. Works as expected.
5.3-5 \*‣ \*( m, s ) | ( method ) |
‣ \*( s, m ) | ( method ) |
Returns: the scalar multiple s\(\cdot\)m
For a cmat m and a scalar s. For the format of the scalar see 4.2-1. Works as expected.
5.3-6 \*‣ \*( v, m ) | ( method ) |
Returns: the product v\(\cdot\)m
For a cmat m and a cvec s with the same length as the number of rows of m. Works as expected. Note that there is a very fast method for the case that m is pre-greased (see 5.8).
5.3-7 \^‣ \^( v, m ) | ( method ) |
Returns: the product v\(\cdot\)m
For a cmat m and a cvec s with the same length as the number of rows of m. Works as expected. Note that there is a very fast method for the case that m is pre-greased (see 5.8).
5.3-8 \*‣ \*( m, n ) | ( method ) |
Returns: the product m\(\cdot\)n
Of course, the cmat m must have as many columns as the cmat n has rows. Works as expected. Note that there is a very fast method for the case that n is pre-greased (see 5.8).
‣ ZeroSameMutability( m ) | ( method ) |
Returns: the zero cmat over the same field and with the same dimensions as m
m must be a cmat.
‣ ZeroMutable( m ) | ( method ) |
Returns: a mutable copy of the zero cmat over the same field and with the same dimensions as m
m must be a cmat.
‣ OneSameMutability( m ) | ( method ) |
Returns: the identity cmat over the same field and with the same dimensions as m
m must be a square cmat.
‣ OneMutable( m ) | ( method ) |
Returns: a mutable copy of the identity cmat over the same field and with the same dimensions as m
m must be a square cmat.
‣ InverseMutable( m ) | ( method ) |
Returns: the multiplicative inverse of m
If the cmat is not square or not invertible then fail is returned. Behaves exactly as expected.
‣ InverseSameMutability( m ) | ( method ) |
Returns: the multiplicative inverse of m
If the cmat is not square or not invertible then fail is returned. Behaves exactly as expected.
‣ TransposedMat( m ) | ( method ) |
Returns: the transpose of m
Behaves exactly as expected.
‣ KroneckerProduct( m, n ) | ( method ) |
Returns: the Kronecker product of m and n
Behaves exactly as expected.
‣ =( m, n ) | ( method ) |
Returns: true or false
Returns true if the cmats m and n are equal. The matrices must be over the same field and must have equal dimensions.
‣ LT( m, n ) | ( method ) |
Returns: true or false
Returns true if the cmat m is smaller than n. The matrices must be over the same field and must have equal dimensions. The method implements the lexicographic order and uses LT for the ordering of vectors. Note that the operation LT is the same as \<.
‣ IsZero( m ) | ( method ) |
Returns: true or false
Returns true if the cmat m is equal to zero, meaning that all entries are equal to zero.
‣ IsOne( m ) | ( method ) |
Returns: true or false
Returns true iff the cmat m is equal to the identity matrix.
‣ IsDiagonalMat( m ) | ( method ) |
Returns: true or false
Returns true iff the cmat m is a diagonal matrix.
‣ IsUpperTriangularMat( m ) | ( method ) |
Returns: true or false
Returns true iff the cmat m is an upper triangular matrix.
‣ IsLowerTriangularMat( m ) | ( method ) |
Returns: true or false
Returns true iff the cmat m is a lower triangular matrix.
‣ CVEC_HashFunctionForCMats( m, data ) | ( function ) |
Returns: an integer hash value
This is a hash function usable for the ChooseHashFunction (orb: ChooseHashFunction) framework. It takes as arguments a cmat m and a list data of length \(2\). The first entry of data is the length of the hash table used and the second entry is the number of bytes looked at in the cvecs in the matrices.
‣ ChooseHashFunction( m, l ) | ( method ) |
Returns: a record with entries func and data.
Chooses a hash function to be used for cmats like m (that is, over the same field with the same number of columns) and for hash tables of length l. The hash function itself is stored in the func component of the resulting record. The hash function has to be called with two arguments: the first must be a matrix like m and the second must be the value of the data component of the resulting record.
As described in Section 5.2 you can use the slicing operator \{\} for read and write access of a subset of the rows of a cmat. However, the double slicing operator is not supported. The reason for this is twofold: First there is a technical issue that the double slicing operator cannot easily be overloaded in the GAP system. The second is, that very often the double slicing operator is used to copy a part of one matrix to another part of another matrix using double slicing on both sides of an assignment. This is quite inefficient because it creates an intermediate object, namely the submatrix which is extracted.
Therefore we have chosen to support submatrix access through two operations ExtractSubMatrix (5.5-1) and CopySubMatrix (5.5-2) described below.
‣ ExtractSubMatrix( m, rows, cols ) | ( operation ) |
Returns: a submatrix of m
This operation extracts the submatrix of the matrix m consisting of the rows described by the integer list (or range) rows and of the columns described by the integer list (or range) cols. This is thus equivalent to the usage m{rows}{cols}. Note that the latter does not work for cmats, whereas a quite efficient method for ExtractSubMatrix is available for cmats.
‣ CopySubMatrix( src, dst, srows, drows, scols, dcols ) | ( operation ) |
Returns: nothing
This operation extracts the submatrix of the matrix src consisting of the rows described by the integer list (or range) srows and of the columns described by the integer list (or range) scols and copies it into the submatrix of dst described by the integer lists (or ranges) drows and dcols. No intermediate object is created. This is thus equivalent to the usage dst{drows}{dcols} := src{srows}{scols}. Note that the latter does not work for cmats, whereas a quite efficient method for CopySubMatrix is available for cmats.
‣ BaseField( m ) | ( method ) |
Returns: the base field of m
For a cmat m this returns the GAP object GF(p,d) corresponding to the base field of m. Note that this is a relatively fast lookup.
‣ Characteristic( m ) | ( method ) |
Returns: the characteristic of the base field of m
Returns the characteristic of the base field of m (see BaseField (5.6-1)).
‣ DegreeFFE( m ) | ( method ) |
Returns: the degree of the base field of m over its prime field
Returns the degree of the base field of m over its prime field (see BaseField (5.6-1)).
‣ DefaultField( m ) | ( method ) |
Returns: the base field of m
For a cmat m this returns the GAP object GF(p,d) corresponding to the base field of m. Note that this is a relatively fast lookup.
‣ CVEC_WriteMat( f, m ) | ( method ) |
Returns: true or fail
f must be a file object from the IO package (see IsFile (IO: IsFile)) and m must be a cmat. The matrix m is written to the file f. Note that the format (see Section 3.4) is platform independent, such that matrices can be exchanged between different architectures. The result is true or fail depending on whether everything worked or an error occurred respectively.
‣ CVEC_WriteMatToFile( fn, m ) | ( method ) |
Returns: true or fail
fn must be a string object containing a file name and m must be a cmat. The matrix m is written to the file with name fn on the local storage. Note that the format (see Section 3.4) is platform independent, such that matrices can be exchanged between different architectures. The result is true or fail depending on whether everything worked or an error occurred respectively.
‣ CVEC_WriteMatsToFile( fnpref, l ) | ( method ) |
Returns: true or fail
fnpref must be a string object containing a file name prefix and m must be a list of cmats. The matrices in l are written to the files with names determined by using the string fnpref and appending the natural numbers from \(1\) to the length of l on the local storage. Note that the format (see Section 3.4) is platform independent, such that matrices can be exchanged between different architectures. The result is true or fail depending on whether everything worked or an error occurred respectively.
‣ CVEC_ReadMat( f ) | ( method ) |
Returns: a cmat or fail
f must be a file object from the IO package (see IsFile (IO: IsFile)). A matrix is read from the file f. Note that the format (see Section 3.4) is platform independent, such that matrices can be exchanged between different architectures. The result is fail if an error occurred.
‣ CVEC_ReadMatFromFile( fn ) | ( method ) |
Returns: a cmat or fail
fn must be a string object containing a file name. A matrix is read from the file with name fn on the local storage. Note that the format (see Section 3.4) is platform independent, such that matrices can be exchanged between different architectures. The result is fail if an error occurred.
‣ CVEC_ReadMatsFromFile( fnpref ) | ( method ) |
Returns: a list of cmats or fail
fnpref must be a string object containing a file name prefix. A list of matrices is read from the files with names determined by using the string fnpref and appending the natural numbers from \(1\) on from the local storage. The number of matrices read is determined by the highest number such that the corresponding filename exists in the filesystem. Note that the format (see Section 3.4) is platform independent, such that matrices can be exchanged between different architectures. The result is fail if an error occurred.
The basic idea behind the grease
technique is that over a finite field there are only finitely many linear combinations of a fixed list of vectors. Thus, many operations including matrix multiplication can be speeded up by precomputing all possible linear combinations and then just looking up the right one. For the case of matrix multiplication this can for example gain a factor of about \(4\) over the field with \(2\) elements using grease level\(8\)
, which means that for blocks of \(8\) rows all linear combinations are precomputed.
The cvec uses grease whenever appropriate automatically for example for matrix multiplication. However, occasionally the user has to take a conscious decision, which matrices to grease, because this of course uses more memory.
A cmat can be pre-greased
with level \(l\), which means that it is chopped into chunks of \(l\) rows and for each such chunk all possible linear combinations are precomputed and stored. This increases the memory used to store the matrix by a factor of \(q^l\) if the base field of the matrix has \(q\) elements. However, operations like vector matrix multiplication and matrix matrix multiplication (here the right hand side matrix must be greased!) are speeded up. As a rule of thumb the factor one can hope for is about \(l \cdot (q-1)/q\). Note that for big matrices matrix multiplication does greasing on the fly anyway and therefore one cannot hope for such a big factor by pre-greasing.
‣ GreaseMat( m, l ) | ( operation ) |
‣ GreaseMat( m ) | ( operation ) |
Returns: nothing
m must be a cmat. It is pregreased with level l. Without the argument l a grease level depending of the field size is chosen automatically. Note that the matrix will need much more memory when pregreased.
‣ UnGreaseMat( m ) | ( operation ) |
Returns: nothing
m must be a cmat. The pregreased information is deleted. This can save a lot of memory.
‣ Randomize( m ) | ( method ) |
‣ Randomize( m, rs ) | ( method ) |
Returns: the matrix m
m must be a cmat and rs must be a random source object if given. This method changes the matrix m in place by (pseudo) random values in the field over which the matrix lives. If a random source is given, the pseudo random numbers used are taken from this source, otherwise the global random source in the GAP library is taken.
‣ OverviewMat( m ) | ( function ) |
Returns: nothing
An ASCII art overview over the cmat m is printed. Stars indicate nonzero blocks in the matrix and dots zero blocks.
‣ Unpack( m ) | ( method ) |
Returns: a list of lists of finite field elements
This operation unpacks a cmat m. A new plain list of plain lists containing the corresponding numbers as GAP finite field elements. Note that the matrix m remains unchanged.
generated by GAPDoc2HTML