IT++ Logo
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 
51 
52 namespace itpp
53 {
54 
55 // ----------------------------------------------------------------------
56 // Sparse GF(2) matrix class
57 // ----------------------------------------------------------------------
58 
61 
64 
65 
66 // ----------------------------------------------------------------------
67 // Alist parameterization of sparse GF(2) matrix class
68 // ----------------------------------------------------------------------
69 
85 {
86 public:
90  GF2mat_sparse_alist(const std::string &fname);
91 
93  void read(const std::string &fname);
95  void write(const std::string &fname) const;
96 
103  GF2mat_sparse to_sparse(bool transpose = false) const;
104 
112  void from_sparse(const GF2mat_sparse &mat, bool transpose = false);
113 
114 protected:
116  bool data_ok;
118  int M;
120  int N;
122  imat mlist;
124  imat nlist;
126  ivec num_mlist;
128  ivec num_nlist;
133 };
134 
135 
136 // ----------------------------------------------------------------------
137 // Dense GF(2) matrix class
138 // ----------------------------------------------------------------------
139 
157 class GF2mat
158 {
159 public:
160 
161  // ----------- Constructors -----------
162 
164  GF2mat();
165 
167  GF2mat(int m, int n);
168 
170  GF2mat(const GF2mat_sparse &X);
171 
176  GF2mat(const GF2mat_sparse &X, int m1, int n1, int m2, int n2);
177 
186  GF2mat(const GF2mat_sparse &X, const ivec &columns);
187 
195  GF2mat(const bvec &x, bool is_column = true);
196 
198  GF2mat(const bmat &X);
199 
201  void set_size(int m, int n, bool copy = false);
202 
204  GF2mat_sparse sparsify() const;
205 
207  bvec bvecify() const;
208 
209  // ----------- Elementwise manipulation and simple functions -------------
210 
212  inline bin get(int i, int j) const;
213 
215  inline bin operator()(int i, int j) const { return get(i, j); };
216 
218  inline void set(int i, int j, bin s);
219 
221  inline void addto_element(int i, int j, bin s);
222 
224  void set_col(int j, bvec x);
225 
227  void set_row(int i, bvec x);
228 
230  bool is_zero() const;
231 
233  void swap_rows(int i, int j);
234 
236  void swap_cols(int i, int j);
237 
244  void permute_rows(ivec &perm, bool I);
245 
253  void permute_cols(ivec &perm, bool I);
254 
256  GF2mat transpose() const;
257 
259  GF2mat get_submatrix(int m1, int n1, int m2, int n2) const;
260 
262  GF2mat concatenate_horizontal(const GF2mat &X) const;
263 
265  GF2mat concatenate_vertical(const GF2mat &X) const;
266 
268  bvec get_row(int i) const;
269 
271  bvec get_col(int j) const;
272 
274  double density() const;
275 
277  int rows() const { return nrows; }
278 
280  int cols() const { return ncols; }
281 
289  void add_rows(int i, int j);
290 
291  // ---------- Linear algebra --------------
292 
298  GF2mat inverse() const;
299 
301  int row_rank() const;
302 
319  int T_fact(GF2mat &T, GF2mat &U, ivec &P) const;
320 
343  ivec &P, int rank, int r, int c) const;
344 
366  bool T_fact_update_addcol(GF2mat &T, GF2mat &U,
367  ivec &P, bvec newcol) const;
368 
369  // ----- Operators -----------
370 
372  void operator=(const GF2mat &X);
373 
375  bool operator==(const GF2mat &X) const;
376 
377  // ----- Friends ------
378 
380  friend GF2mat operator*(const GF2mat &X, const GF2mat &Y);
381 
383  friend bvec operator*(const GF2mat &X, const bvec &y);
384 
389  friend GF2mat operator+(const GF2mat &X, const GF2mat &Y);
390 
392  friend std::ostream &operator<<(std::ostream &os, const GF2mat &X);
393 
395  friend it_file &operator<<(it_file &f, const GF2mat &X);
396 
398  friend it_ifile &operator>>(it_ifile &f, GF2mat &X);
399 
401  friend GF2mat mult_trans(const GF2mat &X, const GF2mat &Y);
402 
403 private:
404  int nrows, ncols; // number of rows and columns of matrix
405  int nwords; // number of bytes used
406  Mat<unsigned char> data; // data structure
407 
408  // This value is used to perform division by bit shift and is equal to
409  // log2(8)
410  static const unsigned char shift_divisor = 3;
411 
412  // This value is used as a mask when computing the bit position of the
413  // division remainder
414  static const unsigned char rem_mask = (1 << shift_divisor) - 1;
415 };
416 
417 
418 // ----------------------------------------------------------------------
419 // GF2mat related functions
420 // ----------------------------------------------------------------------
421 
426 it_file &operator<<(it_file &f, const GF2mat &X);
427 
432 it_ifile &operator>>(it_ifile &f, GF2mat &X);
433 
438 GF2mat operator*(const GF2mat &X, const GF2mat &Y);
439 
444 bvec operator*(const GF2mat &X, const bvec &y);
445 
450 GF2mat operator+(const GF2mat &X, const GF2mat &Y);
451 
456 std::ostream &operator<<(std::ostream &os, const GF2mat &X);
457 
462 GF2mat gf2dense_eye(int m);
463 
468 GF2mat mult_trans(const GF2mat &X, const GF2mat &Y);
469 
470 
471 // ----------------------------------------------------------------------
472 // Inline implementations
473 // ----------------------------------------------------------------------
474 
475 inline void GF2mat::addto_element(int i, int j, bin s)
476 {
477  it_assert_debug(i >= 0 && i < nrows, "GF2mat::addto_element()");
478  it_assert_debug(j >= 0 && j < ncols, "GF2mat::addto_element()");
479  if (s == 1)
480  data(i, (j >> shift_divisor)) ^= (1 << (j & rem_mask));
481 }
482 
483 inline bin GF2mat::get(int i, int j) const
484 {
485  it_assert_debug(i >= 0 && i < nrows, "GF2mat::get_element()");
486  it_assert_debug(j >= 0 && j < ncols, "GF2mat::get_element()");
487  return (data(i, (j >> shift_divisor)) >> (j & rem_mask)) & 1;
488 }
489 
490 inline void GF2mat::set(int i, int j, bin s)
491 {
492  it_assert_debug(i >= 0 && i < nrows, "GF2mat::set_element()");
493  it_assert_debug(j >= 0 && j < ncols, "GF2mat::set_element()");
494  if (s == 1) // set bit to one
495  data(i, (j >> shift_divisor)) |= (1 << (j & rem_mask));
496  else // set bit to zero
497  data(i, (j >> shift_divisor)) &= (~(1 << (j & rem_mask)));
498 }
499 
500 } // namespace itpp
501 
502 #endif // #ifndef GF2MAT_H
SourceForge Logo

Generated on Fri Mar 21 2014 17:14:12 for IT++ by Doxygen 1.8.1.2