Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members

atlas::bitvector Namespace Reference


Classes

class  atlas::bitvector::BitVector< dim >
 The template class |BitVector<dim>| represents a number |size| with |0<=size<=dim|, and a vector in the (Z/2Z)-vector space (Z/2Z)^size. More...
class  atlas::bitvector::BitVectorList< dim >
class  atlas::bitvector::BitMatrix< dim >
 A matrix of d_rows rows and d_columns columns, with entries in Z/2Z. More...
class  atlas::bitvector::FirstBit< dim >

Functions

template<size_t dim>
void combination (BitVector< dim > &, const std::vector< BitVector< dim > > &, const bitset::BitSet< dim > &)
 Puts in |v| the linear combination of the elements of |b| given by |e|.
template<size_t dim>
bitset::BitSet< dim > combination (const std::vector< bitset::BitSet< dim > > &, const bitset::BitSet< dim > &)
 Returns the linear combination of the elements of |b| given by |coef|.
template<size_t dim>
void combination (bitset::BitSet< dim > &v, const std::vector< bitset::BitSet< dim > > &b, const bitset::BitSet< dim > &coef)
template<size_t dim>
bool firstSolution (bitset::BitSet< dim > &c, const std::vector< BitVector< dim > > &b, const BitVector< dim > &rhs)
 Put into |c| a solution of the system with as left hand sides the rows of a matrix whose columns are given by |b|, and as right hand sides the bits of |rhs|, and return |true|; if no solution exists just return |false|.
template<size_t dimsol, size_t dimeq>
bool firstSolution (BitVector< dimsol > &sol, const std::vector< BitVector< dimeq > > &eqns)
 Either find a solution of the system of equations |eqn|, putting it into |sol| and returning |true|, or return |false| if no solition exists.
template<size_t dim>
void identityMatrix (BitMatrix< dim > &, size_t)
 Puts in m the identity matrix in rank n.
template<size_t dim>
void initBasis (std::vector< BitVector< dim > > &, size_t)
 Initializes b to the canonical basis in dimension n.
template<size_t dim>
void normalize (bitset::BitSet< dim > &, std::vector< BitVector< dim > > &)
 Replaces |b| by the ordered canonical basis of the vector space $V$ it spans. Flags in |t| the set of coordinate positions associated to |b|.
template<size_t dim>
void normalSpanAdd (std::vector< BitVector< dim > > &, std::vector< size_t > &, const BitVector< dim > &)
 Transforms the normal basis defined by the unordered list $a$ into one for the span of $a$ and $v$.
template<size_t dim>
bool scalarProduct (const BitVector< dim > &, const BitVector< dim > &)
 Applies the dual vector vd to v.
template<size_t dim>
void spanAdd (std::vector< BitVector< dim > > &, std::vector< size_t > &, const BitVector< dim > &)
 Enlarges the basis a to span v.


Function Documentation

template<size_t dim>
void combination bitset::BitSet< dim > &  v,
const std::vector< bitset::BitSet< dim > > &  b,
const bitset::BitSet< dim > &  coef
 

Definition at line 42 of file bitvector.h.

Referenced by atlas::subquotient::Subspace< dim >::fromBasis(), atlas::cartanclass::Fiber::grading(), atlas::cartanclass::Fiber::makeStrongReal(), and atlas::subquotient::Subspace< dim >::representative().

template<size_t dim>
bitset::BitSet< dim > atlas::bitvector::combination const std::vector< bitset::BitSet< dim > > &  b,
const bitset::BitSet< dim > &  coef
 

Returns the linear combination of the elements of |b| given by |coef|.

Contrary to the previous case, there is no notion of size for |v|, and there is no need for any particular preparation.

Definition at line 494 of file bitvector_def.h.

template<size_t dim>
void atlas::bitvector::combination BitVector< dim > &  v,
const std::vector< BitVector< dim > > &  b,
const bitset::BitSet< dim > &  e
 

Puts in |v| the linear combination of the elements of |b| given by |e|.

NOTE : it is the caller's responsibility to check that |v| already has the correct size. The right size cannot be determined here if |b.size()=0|.

Definition at line 468 of file bitvector_def.h.

References atlas::bitvector::BitVector< dim >::reset().

Referenced by atlas::bitvector::BitMatrix< dim >::apply(), and atlas::bitvector::BitMatrix< dim >::operator *=().

template<size_t dimsol, size_t dimeq>
bool atlas::bitvector::firstSolution BitVector< dimsol > &  sol,
const std::vector< BitVector< dimeq > > &  eqns
 

Either find a solution of the system of equations |eqn|, putting it into |sol| and returning |true|, or return |false| if no solition exists.

Here |eqns| holds a system of equations, the last bit of each being interpreted as the right hand side.

If there is a solution, |sol| will be resized to to number of indeterminates, which is one less than the size of each equation; however, if the set of equations is empty, |sol| is left unchanged.

Definition at line 596 of file bitvector_def.h.

References normalize(), atlas::bitvector::BitVector< dim >::reset(), atlas::bitvector::BitVector< dim >::resize(), atlas::bitvector::BitVector< dim >::set(), and atlas::bitvector::BitVector< dim >::size().

Referenced by atlas::gradings::findGrading(), atlas::kgb::KGBHelp::grading_seed(), atlas::cartanclass::Fiber::gradingRep(), atlas::cartanset::makeRepresentative(), and atlas::cartanclass::Fiber::makeStrongRepresentatives().

template<size_t dim>
bool atlas::bitvector::firstSolution bitset::BitSet< dim > &  c,
const std::vector< BitVector< dim > > &  b,
const BitVector< dim > &  rhs
 

Put into |c| a solution of the system with as left hand sides the rows of a matrix whose columns are given by |b|, and as right hand sides the bits of |rhs|, and return |true|; if no solution exists just return |false|.

Definition at line 510 of file bitvector_def.h.

References atlas::bitvector::BitVector< dim >::firstBit(), atlas::bitvector::BitVector< dim >::isZero(), atlas::bitset::BitSet< n >::reset(), atlas::bitvector::BitVector< dim >::set(), atlas::bitset::BitSet< n >::set(), atlas::bitvector::BitVector< dim >::size(), and atlas::bitset::BitSet< n >::size().

template<size_t dim>
void atlas::bitvector::identityMatrix BitMatrix< dim > &  m,
size_t  n
 

Puts in m the identity matrix in rank n.

Precondition: n <= dim;

Definition at line 635 of file bitvector_def.h.

References atlas::bitvector::BitMatrix< dim >::reset(), atlas::bitvector::BitMatrix< dim >::resize(), and atlas::bitvector::BitMatrix< dim >::set().

template<size_t dim>
void atlas::bitvector::initBasis std::vector< BitVector< dim > > &  b,
size_t  n
 

Initializes b to the canonical basis in dimension n.

Definition at line 651 of file bitvector_def.h.

References atlas::bitvector::BitMatrix< dim >::set().

template<size_t dim>
void atlas::bitvector::normalize bitset::BitSet< dim > &  t,
std::vector< BitVector< dim > > &  b
 

Replaces |b| by the ordered canonical basis of the vector space $V$ it spans. Flags in |t| the set of coordinate positions associated to |b|.

What is flagged in |t| is the set $J$ in described in the comment for |normalSpanAdd| below. For any $j$, only |b[j]| has a nonzero bit at the position $j'$ of set bit number |j| of |t|; consequently, for any $v\in V$, the coordinate of |b[j]| in $v$ is $v[j']$.

This function works essentially be repeatedly calling |normalSpanAdd| for the vectors of |b|, replacing |b| by the resulting canonical basis at the end. However, the selected coordiante positions |f| do not come out increasingly this way, so we have to sort the canonical basis by leading bit position. This amounts to setting $a'[k]=a[p(k)]$ where $p(0)\ldots,p(l-1)$ is the result of sorting $f[0]\ldots,f[l-1]$ with $l=f.size()=a.size()$.

Definition at line 700 of file bitvector_def.h.

References atlas::polynomials::compare(), normalSpanAdd(), atlas::bitset::BitSet< n >::reset(), atlas::bitset::BitSet< n >::set(), and atlas::bitset::BitSet< n >::swap().

Referenced by firstSolution(), and atlas::bitvector::BitMatrix< dim >::kernel().

template<size_t dim>
void atlas::bitvector::normalSpanAdd std::vector< BitVector< dim > > &  a,
std::vector< size_t > &  f,
const BitVector< dim > &  v
 

Transforms the normal basis defined by the unordered list $a$ into one for the span of $a$ and $v$.

Also updates the list |f| of the same length $l$ as |a| such that |a[i][f[j]]==(i==j?1:0)| for all $i,j<l$.

For each subvectorspace $V$ of $k^d$, let $I$ be a subset of $\{0,\ldots,d-1\}$ such that the standard basis vectors $e_i$ for $i\in I$ generate a complementary subspace $e_I$ to $V$ (one can find such an $I$ by repeatedly throwing in $e_i$s linearly independent to $V$ and previously chosen ones). The normal basis of $V$ corresponding to $I$ is obtained by projecting the $e_j$ for $j$ in the complement $J$ of $I$ onto $V$ along $e_I$ (i.e., according to the direct sum decompostion $k^d=V\oplus e_I$). This can be visualised by viewing $V$ as the function-graph of a linear map from $k^J$ to $k^I$; then the normal basis is the lift to $V$ of the standard basis of $k^J$. We define the canonical basis of $V$ be the normal basis for the complement $I$ of the lexicographically minimal possible set $J$ (lexicographic for the increasing sequences representing the subsets; in fact $I$ is lexicographically maximal since complementation reverses this ordering one fixed-size subsets). One can find this $J$ by repeatedly choosing the smallest index such that the projection from $V$ defined by extracting the coordinates at the selected indices remains surjective.

This function assumes that $a$ already contains the canonical basis of some subspace, and that the elements of |f| describe the corresponding set $J$. We add |v| to the subspace and extend |f|. Then |a| nor |f| are modified if |v| lies in the subspace generated by |a|. Otherwise a new element is added to |a|, a new coordinate index |n| is added to |f|, and the existing vectors in |a| are modified to clear their coordinate |n|.

Definition at line 755 of file bitvector_def.h.

References atlas::bitvector::BitVector< dim >::firstBit(), atlas::bitvector::BitVector< dim >::isZero(), and atlas::bitvector::BitVector< dim >::size().

Referenced by normalize().

template<size_t dim>
bool atlas::bitvector::scalarProduct const BitVector< dim > &  vd,
const BitVector< dim > &  v
 

Applies the dual vector vd to v.

Definition at line 1022 of file bitvector_def.h.

References atlas::bitvector::BitVector< dim >::count().

template<size_t dim>
void atlas::bitvector::spanAdd std::vector< BitVector< dim > > &  a,
std::vector< size_t > &  f,
const BitVector< dim > &  v
 

Enlarges the basis a to span v.

This is a simplified version of |normalSpanAdd|

It is assumed that a contains a list of independent bitvectors all of size |v.size()|; then a reduction of |v| modulo the vectors of |a| is added to the list if |v| was independent, and if it was dependent nothing happens.

Here we still assume that the first set bits of the elements in |a| are all distinct, their positions are indicated in |f|, and bit number |f[i]| is cleared in |a[j]| whenever |i<j|; under these conditions reduction modulo~|a| can be performed by subtracting, for all |i| in increasing order, the vector |a[i]| if bit |f[i]| is currently set. We do not however assume that bit number |f[i]| is cleared in |a[j]| for all |j<i|, and as a consequence we do not need to modify previous vectors |a[i]| to maintain the condition for calling |spanAdd| again; this is the (only) difference with |normalSpanAdd|.

Definition at line 790 of file bitvector_def.h.

References atlas::bitvector::BitVector< dim >::firstBit(), atlas::bitvector::BitVector< dim >::isZero(), and atlas::bitvector::BitVector< dim >::size().

Referenced by atlas::bitvector::BitMatrix< dim >::image().


Generated on Wed Mar 26 16:52:20 2008 for atlas by  doxygen 1.3.9.1