IT++ Logo
gf2mat.h
Go to the documentation of this file.
1 
42 #ifndef GF2MAT_H
43 #define GF2MAT_H
44 
45 #include <itpp/base/vec.h>
46 #include <itpp/base/mat.h>
47 #include <itpp/base/svec.h>
48 #include <itpp/base/smat.h>
49 #include <itpp/base/itfile.h>
50 #include <itpp/itexports.h>
51 
52 namespace itpp
53 {
55 
56 #if (defined(_MSC_VER) && defined(ITPP_SHARED_LIB))
57 //MSVC needs to explicitely instantiate required templates while building the
58 //shared library. Also, these definitions are marked as imported when library is
59 //linked with user's code.
60 
61 template class ITPP_EXPORT Sparse_Mat<bin>;
62 template class ITPP_EXPORT Sparse_Vec<bin>;
63 template class ITPP_EXPORT Mat<unsigned char>;
64 
65 #endif
66 
68 
69 // ----------------------------------------------------------------------
70 // Sparse GF(2) matrix class
71 // ----------------------------------------------------------------------
72 
75 
78 
79 
80 // ----------------------------------------------------------------------
81 // Alist parameterization of sparse GF(2) matrix class
82 // ----------------------------------------------------------------------
83 
98 class ITPP_EXPORT GF2mat_sparse_alist
99 {
100 public:
102  GF2mat_sparse_alist() : data_ok(false) {}
104  GF2mat_sparse_alist(const std::string &fname);
105 
107  void read(const std::string &fname);
109  void write(const std::string &fname) const;
110 
117  GF2mat_sparse to_sparse(bool transpose = false) const;
118 
126  void from_sparse(const GF2mat_sparse &mat, bool transpose = false);
127 
128 protected:
130  bool data_ok;
132  int M;
134  int N;
136  imat mlist;
138  imat nlist;
140  ivec num_mlist;
142  ivec num_nlist;
147 };
148 
149 
150 // ----------------------------------------------------------------------
151 // Dense GF(2) matrix class
152 // ----------------------------------------------------------------------
153 
171 class ITPP_EXPORT GF2mat
172 {
173 public:
174 
175  // ----------- Constructors -----------
176 
178  GF2mat();
179 
181  GF2mat(int m, int n);
182 
184  GF2mat(const GF2mat_sparse &X);
185 
190  GF2mat(const GF2mat_sparse &X, int m1, int n1, int m2, int n2);
191 
200  GF2mat(const GF2mat_sparse &X, const ivec &columns);
201 
209  GF2mat(const bvec &x, bool is_column = true);
210 
212  GF2mat(const bmat &X);
213 
215  void set_size(int m, int n, bool copy = false);
216 
218  GF2mat_sparse sparsify() const;
219 
221  bvec bvecify() const;
222 
223  // ----------- Elementwise manipulation and simple functions -------------
224 
226  inline bin get(int i, int j) const;
227 
229  inline bin operator()(int i, int j) const { return get(i, j); };
230 
232  inline void set(int i, int j, bin s);
233 
235  inline void addto_element(int i, int j, bin s);
236 
238  void set_col(int j, bvec x);
239 
241  void set_row(int i, bvec x);
242 
244  bool is_zero() const;
245 
247  void swap_rows(int i, int j);
248 
250  void swap_cols(int i, int j);
251 
258  void permute_rows(ivec &perm, bool I);
259 
267  void permute_cols(ivec &perm, bool I);
268 
270  GF2mat transpose() const;
271 
273  GF2mat get_submatrix(int m1, int n1, int m2, int n2) const;
274 
276  GF2mat concatenate_horizontal(const GF2mat &X) const;
277 
279  GF2mat concatenate_vertical(const GF2mat &X) const;
280 
282  bvec get_row(int i) const;
283 
285  bvec get_col(int j) const;
286 
288  double density() const;
289 
291  int rows() const { return nrows; }
292 
294  int cols() const { return ncols; }
295 
303  void add_rows(int i, int j);
304 
305  // ---------- Linear algebra --------------
306 
312  GF2mat inverse() const;
313 
315  int row_rank() const;
316 
333  int T_fact(GF2mat &T, GF2mat &U, ivec &P) const;
334 
356  int T_fact_update_bitflip(GF2mat &T, GF2mat &U,
357  ivec &P, int rank, int r, int c) const;
358 
380  bool T_fact_update_addcol(GF2mat &T, GF2mat &U,
381  ivec &P, bvec newcol) const;
382 
383  // ----- Operators -----------
384 
386  void operator=(const GF2mat &X);
387 
389  bool operator==(const GF2mat &X) const;
390 
391  // ----- Friends ------
392 
394  friend ITPP_EXPORT GF2mat operator*(const GF2mat &X, const GF2mat &Y);
395 
397  friend ITPP_EXPORT bvec operator*(const GF2mat &X, const bvec &y);
398 
403  friend ITPP_EXPORT GF2mat operator+(const GF2mat &X, const GF2mat &Y);
404 
406  friend ITPP_EXPORT std::ostream &operator<<(std::ostream &os, const GF2mat &X);
407 
409  friend ITPP_EXPORT it_file &operator<<(it_file &f, const GF2mat &X);
410 
412  friend ITPP_EXPORT it_ifile &operator>>(it_ifile &f, GF2mat &X);
413 
415  friend ITPP_EXPORT GF2mat mult_trans(const GF2mat &X, const GF2mat &Y);
416 
417 private:
418  int nrows, ncols; // number of rows and columns of matrix
419  int nwords; // number of bytes used
420  Mat<unsigned char> data; // data structure
421 
422  // This value is used to perform division by bit shift and is equal to
423  // log2(8)
424  static const unsigned char shift_divisor = 3;
425 
426  // This value is used as a mask when computing the bit position of the
427  // division remainder
428  static const unsigned char rem_mask = (1 << shift_divisor) - 1;
429 };
430 
431 
432 // ----------------------------------------------------------------------
433 // GF2mat related functions
434 // ----------------------------------------------------------------------
435 
440 ITPP_EXPORT it_file &operator<<(it_file &f, const GF2mat &X);
441 
446 ITPP_EXPORT it_ifile &operator>>(it_ifile &f, GF2mat &X);
447 
448 
453 ITPP_EXPORT GF2mat operator*(const GF2mat &X, const GF2mat &Y);
454 
459 ITPP_EXPORT bvec operator*(const GF2mat &X, const bvec &y);
460 
465 ITPP_EXPORT GF2mat operator+(const GF2mat &X, const GF2mat &Y);
466 
471 ITPP_EXPORT std::ostream &operator<<(std::ostream &os, const GF2mat &X);
472 
477 ITPP_EXPORT GF2mat gf2dense_eye(int m);
478 
483 ITPP_EXPORT GF2mat mult_trans(const GF2mat &X, const GF2mat &Y);
484 
485 
486 // ----------------------------------------------------------------------
487 // Inline implementations
488 // ----------------------------------------------------------------------
489 
490 inline void GF2mat::addto_element(int i, int j, bin s)
491 {
492  it_assert_debug(i >= 0 && i < nrows, "GF2mat::addto_element()");
493  it_assert_debug(j >= 0 && j < ncols, "GF2mat::addto_element()");
494  if (s == 1)
495  data(i, (j >> shift_divisor)) ^= (1 << (j & rem_mask));
496 }
497 
498 inline bin GF2mat::get(int i, int j) const
499 {
500  it_assert_debug(i >= 0 && i < nrows, "GF2mat::get_element()");
501  it_assert_debug(j >= 0 && j < ncols, "GF2mat::get_element()");
502  return (data(i, (j >> shift_divisor)) >> (j & rem_mask)) & 1;
503 }
504 
505 inline void GF2mat::set(int i, int j, bin s)
506 {
507  it_assert_debug(i >= 0 && i < nrows, "GF2mat::set_element()");
508  it_assert_debug(j >= 0 && j < ncols, "GF2mat::set_element()");
509  if (s == 1) // set bit to one
510  data(i, (j >> shift_divisor)) |= (1 << (j & rem_mask));
511  else // set bit to zero
512  data(i, (j >> shift_divisor)) &= (~(1 << (j & rem_mask)));
513 }
514 
515 } // namespace itpp
516 
517 #endif // #ifndef GF2MAT_H
SourceForge Logo

Generated on Sat Jul 6 2013 10:54:20 for IT++ by Doxygen 1.8.2