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< GrpNbr >	GrpNbrList
typedef std::vector< unsigned long >	GrpArr
	group element, array repr. More...
typedef std::vector< GrpArr >	GrpArrList
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::BitMap &	cycGenerators (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 matrix::Matrix_base<unsigned long> atlas::abelian::Endomorphism

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.)