IT++ Logo
gf2mat.h
Go to the documentation of this file.
00001 
00042 #ifndef GF2MAT_H
00043 #define GF2MAT_H
00044 
00045 #include <itpp/base/vec.h>
00046 #include <itpp/base/mat.h>
00047 #include <itpp/base/svec.h>
00048 #include <itpp/base/smat.h>
00049 #include <itpp/base/itfile.h>
00050 
00051 
00052 namespace itpp
00053 {
00054 
00055 // ----------------------------------------------------------------------
00056 // Sparse GF(2) matrix class
00057 // ----------------------------------------------------------------------
00058 
00060 typedef Sparse_Vec<bin> GF2vec_sparse;
00061 
00063 typedef Sparse_Mat<bin> GF2mat_sparse;
00064 
00065 
00066 // ----------------------------------------------------------------------
00067 // Alist parameterization of sparse GF(2) matrix class
00068 // ----------------------------------------------------------------------
00069 
00084 class GF2mat_sparse_alist
00085 {
00086 public:
00088   GF2mat_sparse_alist() : data_ok(false) {}
00090   GF2mat_sparse_alist(const std::string &fname);
00091 
00093   void read(const std::string &fname);
00095   void write(const std::string &fname) const;
00096 
00103   GF2mat_sparse to_sparse(bool transpose = false) const;
00104 
00112   void from_sparse(const GF2mat_sparse &mat, bool transpose = false);
00113 
00114 protected:
00116   bool data_ok;
00118   int M;
00120   int N;
00122   imat mlist;
00124   imat nlist;
00126   ivec num_mlist;
00128   ivec num_nlist;
00130   int max_num_m;
00132   int max_num_n;
00133 };
00134 
00135 
00136 // ----------------------------------------------------------------------
00137 // Dense GF(2) matrix class
00138 // ----------------------------------------------------------------------
00139 
00157 class GF2mat
00158 {
00159 public:
00160 
00161   // ----------- Constructors -----------
00162 
00164   GF2mat();
00165 
00167   GF2mat(int m, int n);
00168 
00170   GF2mat(const GF2mat_sparse &X);
00171 
00176   GF2mat(const GF2mat_sparse &X, int m1, int n1, int m2, int n2);
00177 
00186   GF2mat(const GF2mat_sparse &X, const ivec &columns);
00187 
00195   GF2mat(const bvec &x, bool is_column = true);
00196 
00198   GF2mat(const bmat &X);
00199 
00201   void set_size(int m, int n, bool copy = false);
00202 
00204   GF2mat_sparse sparsify() const;
00205 
00207   bvec bvecify() const;
00208 
00209   // ----------- Elementwise manipulation and simple functions -------------
00210 
00212   inline bin get(int i, int j) const;
00213 
00215   inline bin operator()(int i, int j) const { return get(i, j); };
00216 
00218   inline void set(int i, int j, bin s);
00219 
00221   inline void addto_element(int i, int j, bin s);
00222 
00224   void set_col(int j, bvec x);
00225 
00227   void set_row(int i, bvec x);
00228 
00230   bool is_zero() const;
00231 
00233   void swap_rows(int i, int j);
00234 
00236   void swap_cols(int i, int j);
00237 
00244   void permute_rows(ivec &perm, bool I);
00245 
00253   void permute_cols(ivec &perm, bool I);
00254 
00256   GF2mat transpose() const;
00257 
00259   GF2mat get_submatrix(int m1, int n1, int m2, int n2) const;
00260 
00262   GF2mat concatenate_horizontal(const GF2mat &X) const;
00263 
00265   GF2mat concatenate_vertical(const GF2mat &X) const;
00266 
00268   bvec get_row(int i) const;
00269 
00271   bvec get_col(int j) const;
00272 
00274   double density() const;
00275 
00277   int rows() const { return nrows; }
00278 
00280   int cols() const { return ncols; }
00281 
00289   void add_rows(int i, int j);
00290 
00291   // ---------- Linear algebra --------------
00292 
00298   GF2mat inverse() const;
00299 
00301   int row_rank() const;
00302 
00319   int T_fact(GF2mat &T, GF2mat &U, ivec &P) const;
00320 
00342   int T_fact_update_bitflip(GF2mat &T, GF2mat &U,
00343                             ivec &P, int rank, int r, int c) const;
00344 
00366   bool T_fact_update_addcol(GF2mat &T, GF2mat &U,
00367                             ivec &P, bvec newcol) const;
00368 
00369   // ----- Operators -----------
00370 
00372   void operator=(const GF2mat &X);
00373 
00375   bool operator==(const GF2mat &X) const;
00376 
00377   // ----- Friends ------
00378 
00380   friend GF2mat operator*(const GF2mat &X, const GF2mat &Y);
00381 
00383   friend bvec operator*(const GF2mat &X, const bvec &y);
00384 
00389   friend GF2mat operator+(const GF2mat &X, const GF2mat &Y);
00390 
00392   friend std::ostream &operator<<(std::ostream &os, const GF2mat &X);
00393 
00395   friend it_file &operator<<(it_file &f, const GF2mat &X);
00396 
00398   friend it_ifile &operator>>(it_ifile &f, GF2mat &X);
00399 
00401   friend GF2mat mult_trans(const GF2mat &X, const GF2mat &Y);
00402 
00403 private:
00404   int nrows, ncols;            // number of rows and columns of matrix
00405   int nwords;                  // number of bytes used
00406   Mat<unsigned char> data;   // data structure
00407 
00408   // This value is used to perform division by bit shift and is equal to
00409   // log2(8)
00410   static const unsigned char shift_divisor = 3;
00411 
00412   // This value is used as a mask when computing the bit position of the
00413   // division remainder
00414   static const unsigned char rem_mask = (1 << shift_divisor) - 1;
00415 };
00416 
00417 
00418 // ----------------------------------------------------------------------
00419 // GF2mat related functions
00420 // ----------------------------------------------------------------------
00421 
00426 it_file &operator<<(it_file &f, const GF2mat &X);
00427 
00432 it_ifile &operator>>(it_ifile &f, GF2mat &X);
00433 
00438 GF2mat operator*(const GF2mat &X, const GF2mat &Y);
00439 
00444 bvec operator*(const GF2mat &X, const bvec &y);
00445 
00450 GF2mat operator+(const GF2mat &X, const GF2mat &Y);
00451 
00456 std::ostream &operator<<(std::ostream &os, const GF2mat &X);
00457 
00462 GF2mat gf2dense_eye(int m);
00463 
00468 GF2mat mult_trans(const GF2mat &X, const GF2mat &Y);
00469 
00470 
00471 // ----------------------------------------------------------------------
00472 // Inline implementations
00473 // ----------------------------------------------------------------------
00474 
00475 inline void GF2mat::addto_element(int i, int j, bin s)
00476 {
00477   it_assert_debug(i >= 0 && i < nrows, "GF2mat::addto_element()");
00478   it_assert_debug(j >= 0 && j < ncols, "GF2mat::addto_element()");
00479   if (s == 1)
00480     data(i, (j >> shift_divisor)) ^= (1 << (j & rem_mask));
00481 }
00482 
00483 inline bin GF2mat::get(int i, int j) const
00484 {
00485   it_assert_debug(i >= 0 && i < nrows, "GF2mat::get_element()");
00486   it_assert_debug(j >= 0 && j < ncols, "GF2mat::get_element()");
00487   return (data(i, (j >> shift_divisor)) >> (j & rem_mask)) & 1;
00488 }
00489 
00490 inline void GF2mat::set(int i, int j, bin s)
00491 {
00492   it_assert_debug(i >= 0 && i < nrows, "GF2mat::set_element()");
00493   it_assert_debug(j >= 0 && j < ncols, "GF2mat::set_element()");
00494   if (s == 1) // set bit to one
00495     data(i, (j >> shift_divisor)) |= (1 << (j & rem_mask));
00496   else // set bit to zero
00497     data(i, (j >> shift_divisor)) &= (~(1 << (j & rem_mask)));
00498 }
00499 
00500 } // namespace itpp
00501 
00502 #endif // #ifndef GF2MAT_H
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
SourceForge Logo

Generated on Sat Jul 9 2011 15:21:29 for IT++ by Doxygen 1.7.4