Goto Chapter: Top 1 2 3 4 5 6 7 8 9 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

4 Vectors
 4.1 Creation
 4.2 Arithmetic
 4.3 Element access and slicing
 4.4 Comparison of Vectors and other information
 4.5 Changing representation, Unpacking
 4.6 Access to the base field
 4.7 Hashing techniques for cvecs

4 Vectors

See Section 3.2 for a documentation of the data format of cvecs and its restrictions.

4.1 Creation

Note that many functions described later in this chapter implicitly create new cvecs, such that it is usually only in the beginning of a calculation necessary to create cvecs explicitly.

4.1-1 CVec
‣ CVec( arg )( operation )

Returns: a new mutable cvec

Creates a new cvec. See the method descriptions for details.

4.1-2 CVec
‣ CVec( cvecclass )( method )

Returns: a new mutable cvec

cvecclass must be a cvecclass. Creates a new cvec containing only zeroes. For an explanation of the term cvecclass see Section 3.2 and CVecClass (4.1-12).

4.1-3 CVec
‣ CVec( coeffs, cvecclass )( method )

Returns: a new mutable cvec

This method takes a coefficient list and a cvecclass as arguments. Assume the vector will be over \(GF(p,d)\) with \(q=p^d\). For the coefficient list coeffs there exist several possibilities, partially depending on the base field size. The easiest way is to use GAP finite field elements, which will be put into the new vector in the same order. If \(d=1\), one can always use GAP immediate integers between \(0\) and \(p-1\), the vector will then contain the corresponding cosets in \(GF(p)=Z/pZ\). If \(q\) is small enough to be a GAP immediate integer, then one can use GAP immediate integers that are equal to the \(p\)-adic expansion using the coefficients of the representing polynomial as coefficients. That is, if an element in \(GF(p,d)\) is represented by the polynomial \(\sum_{{i=0}}^{{d-1}} a_i x^i\) with \(a_i \in \{0,\ldots,p-1\}\), then one has to put \(\sum_{{i=0}}^{{d-1}} a_i p^i\) as integer into the coefficient list coeffs. If \(q\) is larger, then coeffs must be a list of lists of length \(d\) and contains for each field element of \(GF(p,d)\) in the vector a list of its \(d\) coefficients of the representing polynomial. For an explanation of the term cvecclass see Section 3.2 and CVecClass (4.1-12). Of course, the length of the list coeffs must match the length of the vector given in the cvecclass.

4.1-4 CVec
‣ CVec( coeffs, p, d )( method )

Returns: a new mutable cvec

This method takes a coefficient list and two positive integers p and d as arguments. A new cvec over \(GF(p,d)\) will be created. Let \(q := p^d\).

For a description of the possible values of the coefficient list coeffs see the description of the method CVec (4.1-3).

4.1-5 CVec
‣ CVec( v )( method )

Returns: a new cvec

v must be a GAP compressed vector either over \(GF(2)\) or \(GF(p,d)\) with \(p^d \leq 256\). Creates a new cvec containing the same numbers as v over the field which the Field operation returns for v.

4.1-6 CVec
‣ CVec( coeffs, f )( method )

Returns: a new mutable cvec

This method takes a coefficient list and a finite field f as arguments. A new cvec over f will be created. Let \(q := \)Size(f).

For a description of the possible values of the coefficient list coeffs see the description of the method CVec (4.1-3).

After having encountered the concept of a cvecclass already a few times it is time to learn how to create one. The following operation is used first to create new cvecclasses and second to ask a cvec for its class. In addition, it is used for cscas.

4.1-7 CVecClass
‣ CVecClass( arg )( operation )

Returns: a cvecclass

Creates new cvecclasses and asks cvecs for their class. See the following method descriptions for details. For an explanation of the term cvecclass see Section 3.2.

4.1-8 CVecClass
‣ CVecClass( p, d, l )( method )

Returns: a cvecclass

All three arguments must be integers. The arguments p and d must be positive and describe the base field \(GF(p,d)\). The third argument must be non-negative and the method returns the cvecclass of vectors over \(GF(p,d)\) of length l.

For an explanation of the term cvecclass and its data structure see Section 3.2.

4.1-9 CVecClass
‣ CVecClass( v )( method )

Returns: a cvecclass

The argument v must be a cvec. The method returns the corresponding cvecclass. For an explanation of the term cvecclass and its data structure see Section 3.2.

4.1-10 CVecClass
‣ CVecClass( v, l )( method )

Returns: a cvecclass

The argument v must be a cvec. The method returns the corresponding cvecclass for vectors over the same field as v but with length l. This is much faster than producing the same object by giving \(p\) and \(d\). For an explanation of the term cvecclass and its data structure see Section 3.2.

4.1-11 CVecClass
‣ CVecClass( c, l )( method )

Returns: a cvecclass

The argument c must be a cvecclass. The method returns the corresponding cvecclass for vectors over the same field as those in c but with length l. This is much faster than producing the same object by giving \(p\) and \(d\). For an explanation of the term cvecclass and its data structure see Section 3.2.

4.1-12 CVecClass
‣ CVecClass( f, l )( method )

Returns: a cvecclass

The argument f must be a finite field. The method returns the corresponding cvecclass for vectors over the field f with length l. For an explanation of the term cvecclass and its data structure see Section 3.2.

4.1-13 ZeroSameMutability
‣ ZeroSameMutability( v )( method )

Returns: the zero cvec in the same cvecclass as v

v must be a cvec.

4.1-14 ShallowCopy
‣ ShallowCopy( v )( method )

Returns: a mutable copy of v

v must be a cvec.

4.1-15 Randomize
‣ Randomize( v )( method )
‣ Randomize( v, rs )( method )

Returns: the vector v

v must be a cvec and rs must be a random source object if given. This method changes the vector v in place by (pseudo) random values in the field over which the vector 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.

4.2 Arithmetic

Of course, the standard arithmetic infix operations \(+\), \(-\) and \(*\) (for vectors and scalars) work as expected by using the methods below. We start this section with a subsection on the usage of scalars in arithmetic operations involving vectors.

4.2-1 Handling of scalars in arithmetic operations

In all places (like in \*) where vectors and scalars occur, the following conventions apply to scalars:

GAP finite field elements can be used as scalars.

Integers between \(0\) and \(p-1\) (inclusively) can always be used as scalars representing prime field elements via the isomorphism \(GF(p)=Z/pZ\), also for extension fields. Larger integers than \(p-1\), as long as they are GAP immediate integers, are interpreted as the \(p\)-adic expansion of the coefficient list of the polynomial representing the scalar. Note that this usage of immediate integers differs from the standard list arithmetic in GAP because multiplication with the integer \(n\) not necessarily means the same than \(n\) times addition! Larger integers than immediate integers are not supported.

4.2-2 \+
‣ \+( v, w )( method )

Returns: the sum \(\textit{v}+\textit{w}\) as a new cvec

For two cvecs v and w. Works as expected.

4.2-3 \-
‣ \-( v, w )( method )

Returns: the difference \(\textit{v}-\textit{w}\) as a new cvec

For two cvecs v and w. Works as expected.

4.2-4 AdditiveInverseSameMutability
‣ AdditiveInverseSameMutability( v )( method )
‣ \-( v )( method )

Returns: the additive inverse of v as a new cvec

For a cvec v. Works as expected.

4.2-5 AdditiveInverseMutable
‣ AdditiveInverseMutable( v )( method )

Returns: the additive inverse of v as a new mutable cvec

For a cvec v. Works as expected.

4.2-6 \*
‣ \*( v, s )( method )
‣ \*( s, v )( method )

Returns: the scalar multiple s\(\cdot\)v

For a cvec v and a scalar s. For the format of the scalar see 4.2-1. Works as expected.

4.2-7 AddRowVector
‣ AddRowVector( v, w, s )( method )
‣ AddRowVector( v, w, s, fr, to )( method )

Returns: nothing

v and w must be cvecs over the same field with equal length, s a scalar (see Subsection 4.2-1) and v must be mutable. Adds s\(\cdot\)w to v modifying v. If fr and to are given, they give a hint, that w is zero outside positions fr to to (inclusively). The method can, if it chooses so, save time by not computing outside that range. In fact, the implemented method restricts the operation to the Words involved.

If either fr or to is \(0\) it defaults to \(1\) and Length(v) respectively.

4.2-8 MultVector
‣ MultVector( v, s )( method )
‣ MultVector( v, s, fr, to )( method )

Returns: nothing

v must be a mutable cvec and s a scalar (see Subsection 4.2-1). Multiplies v by s modifying v. If fr and to are given, they give a hint, that v is zero outside positions fr to to (inclusively). The method can, if it chooses so, save time by not computing outside that range. In fact, the implemented method restricts the operation to the Words involved.

If either fr or to is \(0\) it defaults to \(1\) and Length(v) respectively.

4.2-9 ScalarProduct
‣ ScalarProduct( v, w )( method )

Returns: the scalar product

Both v and w must be cvecs over the same field with equal length. The function returns the scalar product of the two vectors. Note that there is a very efficient method for prime fields with \(p < 65536\). In the other cases the method taken is not extremely fast.

4.2-10 ZeroMutable
‣ ZeroMutable( v )( method )

Returns: a mutable copy of the zero cvec in the same cvecclass as v

v must be a cvec.

4.2-11 ZeroVector
‣ ZeroVector( l, v )( method )

Returns: a mutable copy of the zero cvec over the same field than v but with length l

v must be a cvec and l a GAP integer.

4.3 Element access and slicing

cvecs behave to some extend like lists with respect to element access and slicing. However, they allow only actions that can be implemented efficiently and that do not change their length. In addition there is a highly optimised function to copy contiguous sections of cvecs into another cvec.

4.3-1 ELM_LIST
‣ ELM_LIST( v, pos )( method )

Returns: a finite field element

This is a method for (reading) element access of vectors. v must be a cvec and pos must be a positive integer not greater than the length of v. The finite field element at position pos in v is returned.

Note that the list access syntax v[pos] triggers a call to the ELM_LIST operation.

4.3-2 ASS_LIST
‣ ASS_LIST( v, pos, s )( method )

Returns: nothing

This is a method for (writing) element access of vectors. v must be a cvec and pos must be a positive integer not greater than the length of v. s must be a finite field element or an integer. The finite field element at position pos in v is set to s.

The scalar s is treated exactly as described in Subsection 4.2-1.

Note that the list access syntax v[pos] := s triggers a call to the ASS_LIST operation.

4.3-3 ELMS_LIST
‣ ELMS_LIST( v, l )( method )

Returns: a cvec

This is a method for (reading) slice access of vectors. v must be a cvec and l must be a range object or a list of positive integers not greater than the length of v. In both cases the list of numbers must be contiguous list of valid positions in the vector. A new cvec over the same field as v and with the same length as l is created and returned. The finite field element at i positions l in v are copied into the new vector.

Note that the list slice access syntax v{l} triggers a call to the ELMS_LIST operation.

Note that there intentionally is no write slice access to cvecs, because in most cases this would lead to code that unnecessarily copies data around in an expensive way. Please use the following function instead:

4.3-4 CVEC_Slice
‣ CVEC_Slice( src, dst, srcpos, len, dstpos )( function )

Returns: nothing

src and dst must be cvecs over the same field. The field elements from positions srcpos to \(\textit{srcpos}+\textit{len}-1\) in src are copied to positions from dstpos in dst. Of course all positions must be within the vectors.

Note that this functions is quite efficient, however, the ranges are checked. If you want to avoid this, use CVEC_SLICE instead (with same calling convention), but do not complain later if crashes occur in case of illegal positions used.

4.3-5 CopySubVector
‣ CopySubVector( src, dst, srcposs, dstposs )( method )

Returns: nothing

Implements the operation CopySubVector (Reference: CopySubVector) for cvecs src and dst, that is, srcposs and dstposs must be ranges or plain lists of integers of equal length such that all numbers contained lie between \(1\) and the length of src and dst respectively. The result is undefined if src and dst are the same objects. The method is particularly efficient if both srcposs and dstposs are ranges with increment \(1\).

4.3-6 CVEC_Concatenation
‣ CVEC_Concatenation( arg )( method )

Returns: a new cvec by concatenating all arguments

This function provides concatenation of cvecs over the same base field. The result is a new cvec. A variable number of cvecs over the same field can be given.

4.4 Comparison of Vectors and other information

4.4-1 =
‣ =( v, w )( method )

Returns: true or false

Returns true if the cvecs v and w are equal. The vectors must be over the same field and must have equal length.

4.4-2 LT
‣ LT( v, w )( method )

Returns: true or false

Returns true if the cvec v is smaller than w. The vectors must be over the same field and must have equal length. The order implemented is very efficient but is not compatible with lexicographic ordering of lists of finite field elements! This method should therefore only be used for binary search purposes. Note that the operation LT is the same as \<.

4.4-3 IsZero
‣ IsZero( v )( method )

Returns: true or false

Returns true if the cvec v is equal to zero, meaning that all entries are equal to zero.

4.4-4 PositionNonZero
‣ PositionNonZero( v )( method )

Returns: a positive integer

Returns the index of the first entry in the cvec v that is not equal to zero. If the vector is equal to zero, then its Length plus one is returned.

4.4-5 PositionLastNonZero
‣ PositionLastNonZero( v )( method )

Returns: a non-negative integer

Returns the index of the last entry in the cvec v that is not equal to zero. If the vector is equal to zero, then \(0\) is returned.

4.4-6 Length
‣ Length( v )( method )

Returns: a non-negative integer

Returns the length of the cvec v.

4.5 Changing representation, Unpacking

4.5-1 Unpack
‣ Unpack( v )( method )

Returns: a list of finite field elements

This operation unpacks a cvec v. A new plain list containing the corresponding numbers as GAP finite field elements. Note that the vector v remains unchanged.

4.5-2 IntegerRep
‣ IntegerRep( v )( method )

Returns: a list of integers or of lists of integers

This operation unpacks a cvec v into its integer representation. A new plain list containing the corresponding numbers of the vector is returned. The integer representation of a finite field element is either one integer (containing the p-adic expansion of the polynomial representative of the residue class modulo the Conway polynomial, if the field has less or equal to \(65536\) elements. For larger finite fields each field element is represented as a list of \(d\) integers between \(0\) and \(p-1\), where \(d\) is the degree of the finite field over its prime field. Note that the vector v remains unchanged.

4.5-3 NumberFFVector
‣ NumberFFVector( v, sz )( method )

Returns: an integer

This implements the library operation NumberFFVector (Reference: NumberFFVector). Note that only the case that sz is the number of elements in the base field of v is implemented. There is an inverse operation called CVecNumber (4.5-4).

4.5-4 CVecNumber
‣ CVecNumber( nr, cl )( operation )
‣ CVecNumber( nr, p, d, l )( operation )

Returns: a cvec

This is the inverse operation to NumberFFVector (Reference: NumberFFVector). Of course, the base field of the vector and its length has to be specified, either by giving a cvecclass cl or the parameters p, d, and l. For both cases corresponding methods are available.

4.6 Access to the base field

4.6-1 BaseDomain
‣ BaseDomain( v )( method )

Returns: the base field of v

For a cvec v this returns the GAP object GF(p,d).

4.6-2 BaseField
‣ BaseField( v )( method )

Returns: the base field of v

For a cvec v this returns the GAP object GF(p,d).

4.6-3 Characteristic
‣ Characteristic( v )( method )

Returns: the characteristic of the base field of v

Returns the characteristic of the base field of v (see BaseField (4.6-2)).

4.6-4 DegreeFFE
‣ DegreeFFE( v )( method )

Returns: the degree of the base field of v over its prime field

Returns the degree of the base field of v over its prime field (see BaseField (4.6-2)).

4.7 Hashing techniques for cvecs

4.7-1 CVEC_HashFunctionForCVecs
‣ CVEC_HashFunctionForCVecs( v, data )( function )

Returns: an integer hash value

This is a hash function usable for the ChooseHashFunction (orb: ChooseHashFunction) framework. It takes as arguments a cvec v 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 cvec.

4.7-2 ChooseHashFunction
‣ ChooseHashFunction( v, hashlen )( method )

Returns: a record describing a hash function

Chooses a hash function to store cvecs like v in a hash table of length hashlen. The return value is a record with components func and data bound to CVEC_HashFunctionForCVecs (4.7-1) and a list of length \(2\) to be given as a second argument to CVEC_HashFunctionForCVecs (4.7-1). This allows to use cvecs in the ChooseHashFunction (orb: ChooseHashFunction) framework.

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 Bib Ind

generated by GAPDoc2HTML