atlas  0.6
subquotient.h
Go to the documentation of this file.
1 /*
2  This is subquotient.h
3 
4  Copyright (C) 2004,2005 Fokko du Cloux
5  part of the Atlas of Lie Groups and Representations
6 
7  For license information see the LICENSE file
8 */
9 
10 // Classes |Subspace| and |Subquotient| (for vector spaces over $\Z/2\Z$)
11 
12 #ifndef SUBQUOTIENT_H /* guard against multiple inclusions */
13 #define SUBQUOTIENT_H
14 
15 #include <cassert>
16 
17 #include "../Atlas.h"
18 
19 #include "bitvector.h" // containment
20 
21 /******** function declarations **********************************************/
22 
23 namespace atlas {
24 
25 namespace subquotient {
26 
27 template<size_t dim>
28  BitMatrix<dim> subquotientMap
29  (const Subquotient<dim>&,
30  const Subquotient<dim>&,
31  const BitMatrix<dim>&);
32 
33 
34 /******** type definitions **************************************************/
35 
36 
37 
38 /* Object representing a subspace of (Z/2Z)^d_rank in standard form.
39 
40  Elements of the vector space are |BitVector|s of capacity |dim| and actual
41  size |d_rank|. The subspace is recorded by its (unique) ordered canonical
42  basis |d_basis|. This means its vectors are reduced (in the sense of
43  row-reduced matrices); that is (in the binary case) in the position of the
44  leading (nonzero) bit of each vector, the other vectors heve a bit $0$, and
45  the vectors are ordered by increasing position of their leading bit.
46 
47  The locations of the leading bits are flagged by the |BitSet| |d_support|
48  (of capacity |d_rank|); the number of set bits in |d_support| is equal to
49  the dimension |d_basis.size()| of the |Subspace|.
50 */
51 template<size_t dim> class Subspace
52 {
53  BitVectorList<dim> d_basis;
54  BitSet<dim> d_support;
55  unsigned short int d_rank;
56 
57  public:
58 
59 // constructors and destructors
60 
61  // dummy constructor needed for constructing |Subquotient|, |CartanClass|
62  Subspace() : d_basis(), d_support(), d_rank(0) {}
63 
64  explicit Subspace(size_t n) : d_basis(), d_support(), d_rank(n) {}
65 
66  Subspace(const BitVectorList<dim>&, size_t);
67  Subspace(const BitMatrix<dim>&); // column span
68 
69 // copy, assignment: the implicitly generated versions will do fine
70 
71 // accessors
72  const BitVector<dim>& basis(size_t j) const
73  {
74  assert(j<d_rank);
75  return d_basis[j];
76  }
77 
78  const BitVectorList<dim>& basis() const { return d_basis; }
79  size_t dimension() const { return d_basis.size(); }
80  const size_t rank() const { return d_rank; }
81  const BitSet<dim>& support() const { return d_support; }
82 
83  // reverse-canonical basis of perpendicular subspace of dual
84  BitVectorList<dim> basis_perp () const;
85  BitSet<dim> support_perp () const // complement of |d_support|
86  { return BitSet<dim>(d_support).complement(rank()); } // copy and complement
87 
89  BitVector<dim> toBasis(BitVector<dim> v) // by-value
90  const
91  {
92  assert(contains(v)); // implies |assert(v.size()==rank())|
93  v.slice(support()); // express |v| in |d_basis|
94  assert(v.size()==dimension());
95 
96  return v;
97  }
98 
102  BitVector<dim> fromBasis(const BitVector<dim>& v) const
103  {
104  assert(v.size()==dimension());
105 
106  // expand linear combination of basis given by |v|
107  return bitvector::combination(d_basis,rank(),v.data());
108  }
109 
110  bool contains(const BitVector<dim>& v) const;
111  bool contains(const BitVectorList<dim>& m) const;
112 
113  // the following methods reduce (finding representative) MODULO the subspace
114  BitVector<dim>
115  representative(const BitVector<dim>&) const;
116 
117  BitVector<dim> mod_image(const BitVector<dim>& w)
118  const
119  {
120  return representative(w);
121  }
122  // destructive version
123  void mod_reduce(BitVector<dim>& w) const { w=mod_image(w); }
124 
125 // manipulators
126  void apply (const BitMatrix<dim>&);
127 
128  void swap(Subspace&);
129 
130 }; // |class Subspace|
131 
132 /* Object representing a quotient of two subspaces of (Z/2Z)^d_rank.
133 
134  Elements of the vector space are |BitVector|'s of capacity |dim|; the first
135  |d_rank| coordinates are significant. (The number |d_rank| is contained both
136  in |d_space| and in |d_subspace|, not directly in |Subquotient|. The number
137  is accessible by the public member function |rank()|.) The larger subspace
138  is specified by the |Subspace d_space|. The smaller subspace is specified by
139  the |Subspace d_subspace| (not extremely enlightening names).
140 
141  A consequence of the fact that |d_subspace| is contained in |d_space| is
142  that the collection of leading bits for |d_subspace| is a subset of the
143  collection of leading bits for |d_space|. The \emph{difference} between two
144  sets is flagged by the |BitSet d_support|. The number of set bets in
145  |d_support| is therefore the dimension of the subquotient.
146  */
147 template<size_t dim> class Subquotient
148 {
149  Subspace<dim> d_space; // larger space, expressed as a |Subspace|.
150  Subspace<dim> d_subspace; // smaller space, expressed as a Subspace.
151 
152 /* The field |d_rel_support| flags the row-reduced basis vectors for |d_space|
153  that span the canonical complement to the (smaller) |d_subspace|.
154 
155  The bits are set at the positions indexing the basis vectors whose leading
156  bits do _not_ appear as leading bits of row-reduced basis vectors for the
157  smaller space. The flagged set of basis vectors for |d_space| constitute a
158  basis for a cross section of the subquotient in the larger space. In
159  particular, the number of set bits is equal to the dimension of the
160  subquotient.
161 
162  Note that what is flagged is are numbers of basis vectors of the larger
163  space, _not_ the positions of their leading bits in $(Z/2Z)^n$. Consequently
164  the effective number of bits is |d_space.dimension()| rather than |rank()|,
165  although this number is not recorded in the value |d_rel_support| itself.
166 
167 
168  Example: d_space=(1010,0110,0001) d_space.support={0,1,3}
169  d_subspace=(0111) d_subspace.support={1}
170  d_rel_support={0,2} (corresponding to the basis vectors 1010
171  and 0001 for d_space spanning the canonical complement to
172  d_subspace).
173  */
174 BitSet<dim> d_rel_support;
175 
176  public:
177 
178 // constructors and destructors
179  Subquotient() : d_space(),d_subspace(), d_rel_support() {}
180 
181  explicit Subquotient(size_t n)
182  : d_space(n), d_subspace(n), d_rel_support()
183  {}
184 
185 // Construct a subquotient of $(Z/2Z)^n$
186 // namely the space generated by |bsp| modulo the space generated by |bsub|
187  Subquotient(const BitVectorList<dim>& bsp,
188  const BitVectorList<dim>& bsub, size_t n);
189 
190 // copy, assignment: the implicitly generated versions will do fine
191 
192 // accessors
193 
194  // Dimension of the subquotient.
195  size_t dimension() const
196  { return d_space.dimension() - d_subspace.dimension(); }
197 
198  // Dimension of the ambient vector space in which subquotient is defined
199  size_t rank() const { return d_space.rank(); }
200 
201  const Subspace<dim>& space() const { return d_space; } // numerator
202  const Subspace<dim>& denominator() const { return d_subspace; }
203 
204  /* we call this |support| to the outside world, since it flags basis
205  representatives for the quotient among the basis for |d_space| */
206  const BitSet<dim>& support() const { return d_rel_support; }
207 
208  const BitVectorList<dim> basis() const // reprentatives for generators
209  { BitVectorList<dim> result; result.reserve(d_rel_support.count());
210  for (auto it=d_rel_support.begin(); it(); ++it)
211  result.push_back(d_space.basis(*it));
212  return result;
213  }
214 
215  // Cardinality of the subquotient: 2^dimension.
216  unsigned long size() const { return 1ul << dimension(); }
217 
218 /* Replace by the canonical representative of |w| modulo |d_subspace|.
219 
220  It is assumed that |w| belongs to the "numerator" subspace |d_space|. Then
221  all that needs to be done is reduce modulo the "denominator" |d_subspace|.
222  The value remains in $(Z/2Z)^n$; see |toBasis| to express in subquotient.
223 */
224  void mod_reduce(BitVector<dim>& w) const
225  { d_subspace.mod_reduce(w); }
226 
227  // functional version
228  BitVector<dim> mod_image(const BitVector<dim>& w) const
229  { return d_subspace.mod_image(w); }
230 
231  // for testing purposes; the bits that determine the subquotient
232  BitSet<dim> significantBits() const
233  { return d_space.support() - d_subspace.support(); }
234 
235 /* Expresses |v| in the subquotient basis.
236 
237  It is assumed that |v| belongs to |d_space|.
238 
239  We know that the subset of basis vectors of |d_space| selected by
240  |d_rel_support| is independent modulo |d_subspace|, so if |v| is any linear
241  combination of them, it suffices to extract and pack those coefficients. We
242  can reduce to that situation by reducing |v| modulo |d_subspace|, which is
243  what the call to |mod_image| below does; this will clear the bits for the
244  support of |d_subspace|, while not taking us out of |d_space|.
245 */
246  BitVector<dim> toBasis(const BitVector<dim>& v) const
247  {
248  BitVector<dim> result=mod_image(v); // mod out subspace
249 
250  // implied: |assert(d_space.contains(result))|, |result.size()==rank())|
251  result=d_space.toBasis(result); // express |result| in basis of |d_space|
252  assert(result.size()==d_space.dimension());
253 
254  result.slice(d_rel_support); // remove (null) coordinates for |d_subspace|
255  assert(result.size()==dimension()); // i.e., dimension of the subquotient
256 
257  return result;
258  }
259 
260  // interpret |v| in the subspace basis and return an external representative
261  BitVector<dim> fromBasis(BitVector<dim> v) const // by-value
262  {
263  assert(v.size()==dimension());
264 
265  v.unslice(d_rel_support,d_space.dimension()); // insert null coordinates
266  return d_space.fromBasis(v);
267  }
268 
269 // manipulators
270  void apply (const BitMatrix<dim>&);
271 
272  void swap(Subquotient&);
273 
274  }; // |template <size_t dim> class Subquotient|
275 
276 } // |namespace subquotient|
277 
278 } // |namespace atlas|
279 
280 #endif
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|.
Definition: bitvector.cpp:470
const BitVectorList< dim > basis() const
Definition: subquotient.h:208
Subspace()
Definition: subquotient.h:62
BitVector< dim > toBasis(const BitVector< dim > &v) const
Definition: subquotient.h:246
Definition: Atlas.h:189
BitSet< dim > d_rel_support
Definition: subquotient.h:174
size_t dimension() const
Definition: subquotient.h:195
const BitVectorList< dim > & basis() const
Definition: subquotient.h:78
size_t rank() const
Definition: subquotient.h:199
Subquotient(size_t n)
Definition: subquotient.h:181
void swap(Subspace &)
Definition: subquotient.cpp:169
const BitSet< dim > & support() const
Definition: subquotient.h:81
BitVector< dim > fromBasis(BitVector< dim > v) const
Definition: subquotient.h:261
const BitSet< dim > & support() const
Definition: subquotient.h:206
size_t dimension() const
Definition: subquotient.h:79
BitSet< dim > d_support
pivot (leading nonzero bit) positions
Definition: subquotient.h:54
BitVector< dim > mod_image(const BitVector< dim > &w) const
Definition: subquotient.h:117
Subspace< dim > d_space
Definition: subquotient.h:149
BitVectorList< dim > basis_perp() const
Definition: subquotient.cpp:77
BitVector< dim > mod_image(const BitVector< dim > &w) const
Definition: subquotient.h:228
Subquotient()
Definition: subquotient.h:179
const size_t rank() const
Definition: subquotient.h:80
BitVector< dim > toBasis(BitVector< dim > v) const
Expresses |v| in the subspace basis.
Definition: subquotient.h:89
Subspace< dim > d_subspace
Definition: subquotient.h:150
BitVector< dim > fromBasis(const BitVector< dim > &v) const
Interprets |v| in the subspace basis and returns external form.
Definition: subquotient.h:102
BitSet< dim > support_perp() const
Definition: subquotient.h:85
const Subspace< dim > & denominator() const
Definition: subquotient.h:202
Definition: Atlas.h:188
const BitVector< dim > & basis(size_t j) const
Definition: subquotient.h:72
void mod_reduce(BitVector< dim > &w) const
Definition: subquotient.h:123
const Subspace< dim > & space() const
Definition: subquotient.h:201
unsigned long size() const
Definition: subquotient.h:216
unsigned long n
Definition: axis.cpp:77
Definition: Atlas.h:38
BitSet< dim > significantBits() const
Definition: subquotient.h:232
BitMatrix< dim > subquotientMap(const Subquotient< dim > &source, const Subquotient< dim > &dest, const BitMatrix< dim > &m)
Definition: subquotient.cpp:271
Subspace(size_t n)
Definition: subquotient.h:64
BitVector< dim > representative(const BitVector< dim > &) const
Return canonical representative of |v| modulo our subspace.
Definition: subquotient.cpp:124
void apply(const BitMatrix< dim > &)
Definition: subquotient.cpp:152
unsigned short int d_rank
Dimension of the ambient vector space.
Definition: subquotient.h:55
void mod_reduce(BitVector< dim > &w) const
Definition: subquotient.h:224
BitVectorList< dim > d_basis
reduced echelon basis
Definition: subquotient.h:53
bool contains(const BitVector< dim > &v) const
Definition: subquotient.cpp:95
Vertex v
Definition: graph.cpp:116