|
| template<size_t dim> |
| std::ostream & | operator<< (std::ostream &strm, const BitVector< dim > &v) |
| |
| template<size_t dim> |
| BitVector< dim > | combination (const std::vector< BitVector< dim > > &b, size_t n, const BitSet< dim > &e) |
| | Puts in |v| the linear combination of the elements of |b| given by |e|. More...
|
| |
| template<size_t dim> |
| BitSet< dim > | combination (const std::vector< BitSet< dim > > &b, const BitSet< dim > &coef) |
| | Returns the linear combination of the elements of |b| given by |coef|. More...
|
| |
| template<size_t dim> |
| bool | combination_exists (const std::vector< BitVector< dim > > &b, const BitVector< dim > &rhs, BitSet< dim > &c) |
| |
| template<size_t dimsol, size_t dimeq> |
| bool | solvable (const std::vector< BitVector< dimeq > > &eqns, BitVector< dimsol > &sol) |
| | Either find a solution of the system of equations |eqn|, putting it into |sol| and returning |true|, or return |false| if no solution exists. More...
|
| |
| template<size_t dim> |
| void | identityMatrix (BitMatrix< dim > &m, size_t n) |
| | Puts in m the identity matrix in rank n. More...
|
| |
| template<size_t dim> |
| void | initBasis (std::vector< BitVector< dim > > &b, size_t n) |
| | Initializes b to the canonical basis in dimension n. More...
|
| |
| template<size_t dim> |
| void | Gauss_Jordan (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|. More...
|
| |
| template<size_t dim> |
| void | normalSpanAdd (std::vector< BitVector< dim > > &a, std::vector< size_t > &f, const BitVector< dim > &v) |
| |
| template<size_t dim> |
| void | spanAdd (std::vector< BitVector< dim > > &a, std::vector< size_t > &f, const BitVector< dim > &v) |
| | Enlarges the basis |a| so as to span |v|. More...
|
| |
| template<size_t dim> |
| int_Vector | lift (const BitVector< dim > &v) |
| |
| template SmallBitVector | combination (const std::vector< SmallBitVector > &b, size_t n, const BitSet< constants::RANK_MAX > &e) |
| |
| template BitSet< constants::RANK_MAX > | combination (const std::vector< BitSet< constants::RANK_MAX > > &, const BitSet< constants::RANK_MAX > &) |
| |
| template void | Gauss_Jordan (BitSet< constants::RANK_MAX > &t, std::vector< SmallBitVector > &b) |
| |
| template bool | combination_exists (const std::vector< SmallBitVector > &b, const SmallBitVector &rhs, BitSet< constants::RANK_MAX > &c) |
| |
| template bool | solvable (const std::vector< BitVector< constants::RANK_MAX+1 > > &eqns, SmallBitVector &sol) |
| |
| template void | identityMatrix (BitMatrix< constants::RANK_MAX > &, size_t) |
| |
| template void | initBasis (std::vector< SmallBitVector > &, size_t) |
| |
| template int_Vector | lift (const SmallBitVector &v) |
| |
| template void | initBasis< 64ul > (std::vector< BitVector< 64ul > > &b, size_t r) |
| |
| BinaryEquation | make_equation (const SmallBitVector &lhs, bool rhs) |
| |
template<size_t dim>
| void atlas::bitvector::Gauss_Jordan |
( |
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'$ where number |j| among the raised bits of |t| is found; consequently, for any $v V$, the coordinate of |b[j]| in $v$ is $v[j']$.
This function works essentially by 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),p(l-1)$ is the result of sorting $f[0],f[l-1]$ with $l=f.size()=a.size()$.
template<size_t dim>
| void atlas::bitvector::normalSpanAdd |
( |
std::vector< BitVector< dim > > & |
a, |
|
|
std::vector< size_t > & |
f, |
|
|
const BitVector< dim > & |
v |
|
) |
| |
$ such that the standard basis vectors $e_i$ for $i 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 e_I$). This can be visualised by viewing $V$ as the function-graph of a linear map from $k^J$ to $k^I$ (with the coordinates of domain and codomain interwoven at the positions $J$ and $I$, respectively); then the normal basis is the lift to the graph $V$ of the standard basis of $k^J$. We define the canonical basis of $V$ to 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 on 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 to the set of all possible coordinate tuples. (Intersect $V$ with the subspace defined by setting previously selected coordinates to zero; choose the smallest coordinate that can be nonzero.)
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|.
template<size_t dimsol, size_t dimeq>
| bool atlas::bitvector::solvable |
( |
const std::vector< BitVector< dimeq > > & |
eqns, |
|
|
BitVector< dimsol > & |
sol |
|
) |
| |
Either find a solution of the system of equations |eqn|, putting it into |sol| and returning |true|, or return |false| if no solution exists.
Here |eqn| holds a system of equations, the last bit of each being interpreted as the right hand side.
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| so as 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|.
1.8.11
