atlas  0.6
Classes | Typedefs | Functions
atlas::abelian Namespace Reference

Classes

class  FiniteAbelianGroup
 
class  Homomorphism
 

Typedefs

typedef unsigned long long GrpNbr
 element of Abelian group, compact repr. More...
 
typedef std::vector< GrpNbrGrpNbrList
 
typedef std::vector< unsigned long > GrpArr
 group element, array repr. More...
 
typedef std::vector< GrpArrGrpArrList
 
typedef std::vector< unsigned long > GroupType
 
typedef matrix::Matrix_base< unsigned long > Endomorphism
 

Functions

void basis (std::vector< matrix::Vector< int > > &b, const bitmap::BitMap &B, const FiniteAbelianGroup &A)
 
void coset (bitmap::BitMap &C, const bitmap::BitMap &B, GrpNbr x, const FiniteAbelianGroup &A)
 
const bitmap::BitMapcycGenerators (const FiniteAbelianGroup &A)
 
void generateSubgroup (bitmap::BitMap &B, GrpNbr x, const FiniteAbelianGroup &A)
 
void generators (GrpNbrList &gen, const bitmap::BitMap &B, const FiniteAbelianGroup &A)
 
bool isElementaryAbelian (const std::vector< unsigned long > &c)
 
bitmap::BitMap quotReps (const bitmap::BitMap &B, const FiniteAbelianGroup &A)
 
void to_array (GrpArr &a, GrpNbr x, const GroupType &t)
 
void to_array (GrpArr &a, const matrix::Vector< int > &v, const GroupType &t)
 
void toEndomorphism (Endomorphism &e, const matrix::PID_Matrix< int > &q, const FiniteAbelianGroup &A)
 
GrpNbr to_GrpNbr (const GrpArr &a, const GroupType &t)
 
void transpose (Endomorphism &e, const FiniteAbelianGroup &A)
 
bool isElementaryAbelian (const std::vector< arithmetic::Denom_t > &)
 

Typedef Documentation

typedef std::vector<unsigned long> atlas::abelian::GroupType
typedef std::vector<unsigned long> atlas::abelian::GrpArr

group element, array repr.

typedef std::vector<GrpArr> atlas::abelian::GrpArrList
typedef unsigned long long atlas::abelian::GrpNbr

element of Abelian group, compact repr.

typedef std::vector<GrpNbr> atlas::abelian::GrpNbrList

Function Documentation

void atlas::abelian::basis ( std::vector< matrix::Vector< int > > &  b,
const bitmap::BitMap B,
const FiniteAbelianGroup A 
)

Synopsis: writes A/B in canonical form.

Explanation: we see the current group A as a quotient of Z^d, where d is the rank of A, and the generators of the kernel are multiples of the standard basis vectors given by d_type. The bitmap |B| specifies a subgroup by generators through the |GrpNbr| encoding. Then we wish to write the quotient A/B in canonical form (i.e., as a product of cyclic groups with cardinalities dividing each other.) For this, we put in b a scaled Smith normal basis for the inverse image of B in Z^d.

Note that A is not necessarily in canonical form, so even when B is the trivial subgroup this might yield a basis rather different from the kernel basis.

void atlas::abelian::coset ( bitmap::BitMap C,
const bitmap::BitMap B,
GrpNbr  x,
const FiniteAbelianGroup A 
)

Synopsis: puts in C the coset x+B in A.

Precondition: C.capacity() == A.order();

NOTE : this is a straightforward implementation, shifting elements of B individually.

const bitmap::BitMap & atlas::abelian::cycGenerators ( const FiniteAbelianGroup A)

Synopsis: returns a reference to a bitmap containing exactly one generator for each cyclic subgroup of A.

We simply set all bits, then traverse all elements and whenever a bit is set we clear the bits of all elements that generate the same cyclic subgroup as it, namely its multiples by a number relatively prime to its order in |A|. This uses that iterators over a |bitmap::BitMap| adapt to changes to the underlying bitmap during traversal, unlike |bitset::BitSet::iterator|s.

NOTE: it is expected that this function will typically be called repeatedly for the same group. The bitmap is constructed on the first call for the given group, following the principle of lazy evaluation.

void atlas::abelian::generateSubgroup ( bitmap::BitMap B,
GrpNbr  x,
const FiniteAbelianGroup A 
)

Synopsis: transforms B into the subgroup generated by B and x in A.

NOTE : this is a simple-minded implementation; we do not aim for speed.

void atlas::abelian::generators ( GrpNbrList gen,
const bitmap::BitMap B,
const FiniteAbelianGroup A 
)

Synopsis: puts in gen a list of generators of the subgroup B.

bool atlas::abelian::isElementaryAbelian ( const std::vector< arithmetic::Denom_t > &  )
bool atlas::abelian::isElementaryAbelian ( const std::vector< unsigned long > &  c)

Tells if c is all twos.

bitmap::BitMap atlas::abelian::quotReps ( const bitmap::BitMap B,
const FiniteAbelianGroup A 
)
void atlas::abelian::to_array ( GrpArr a,
GrpNbr  x,
const GroupType t 
)

Synopsis: puts the array-form of x in a.

Precondition: x is representable for t (x < prod t[i]); otherwise the result is the expression of x modulo that product.

Explanation: the array-form (relative to type) is the unique expression of x in the variable-radix base defined by type.

void atlas::abelian::to_array ( GrpArr a,
const matrix::Vector< int > &  v,
const GroupType t 
)

Synopsis: reduces v mod d_type.

The only difficulty is to make sure that negative values are reduced in the way that we want.

Precondition: a is set to v.size();

GrpNbr atlas::abelian::to_GrpNbr ( const GrpArr a,
const GroupType t 
)

Synopsis: returns the number-form of a.

Precondition: a is representable as a GrpNbr;

void atlas::abelian::toEndomorphism ( Endomorphism e,
const matrix::PID_Matrix< int > &  q,
const FiniteAbelianGroup A 
)

Synopsis: transforms q into the corresponding Endomorphism.

This just involves rewriting the coeficients as unsigned longs modulo the type factors.

void atlas::abelian::transpose ( Endomorphism e,
const FiniteAbelianGroup A 
)

Synopsis: transposes the endomorphism e.

This is more subtle than one might think; the main point is that when m|n, the transpose of the canonical map Z/nZ -> Z/mZ is the injection Z/mZ -> Z/nZ which takes 1 to n/m. In general, any map Z/nZ -> Z/mZ factors thru Z/dZ, where d = gcd(m,n), so it is a multiple of the map defined by 1 -> m/d; the transpose is the same multiple of 1 -> n/d.

NOTE: this implementation works for homomorphisms between different groups just as well (except that one needs two grouptypes then.)