00001 00043 #ifndef GF2MAT_H 00044 #define GF2MAT_H 00045 00046 #include <itpp/base/vec.h> 00047 #include <itpp/base/mat.h> 00048 #include <itpp/base/svec.h> 00049 #include <itpp/base/smat.h> 00050 #include <itpp/base/itfile.h> 00051 00052 00053 namespace itpp 00054 { 00055 00056 // ---------------------------------------------------------------------- 00057 // Sparse GF(2) matrix class 00058 // ---------------------------------------------------------------------- 00059 00061 typedef Sparse_Vec<bin> GF2vec_sparse; 00062 00064 typedef Sparse_Mat<bin> GF2mat_sparse; 00065 00066 00067 // ---------------------------------------------------------------------- 00068 // Alist parameterization of sparse GF(2) matrix class 00069 // ---------------------------------------------------------------------- 00070 00085 class GF2mat_sparse_alist 00086 { 00087 public: 00089 GF2mat_sparse_alist() : data_ok(false) {} 00091 GF2mat_sparse_alist(const std::string &fname); 00092 00094 void read(const std::string &fname); 00096 void write(const std::string &fname) const; 00097 00104 GF2mat_sparse to_sparse(bool transpose = false) const; 00105 00113 void from_sparse(const GF2mat_sparse &mat, bool transpose = false); 00114 00115 protected: 00117 bool data_ok; 00119 int M; 00121 int N; 00123 imat mlist; 00125 imat nlist; 00127 ivec num_mlist; 00129 ivec num_nlist; 00131 int max_num_m; 00133 int max_num_n; 00134 }; 00135 00136 00137 // ---------------------------------------------------------------------- 00138 // Dense GF(2) matrix class 00139 // ---------------------------------------------------------------------- 00140 00158 class GF2mat 00159 { 00160 public: 00161 00162 // ----------- Constructors ----------- 00163 00165 GF2mat(); 00166 00168 GF2mat(int m, int n); 00169 00171 GF2mat(const GF2mat_sparse &X); 00172 00177 GF2mat(const GF2mat_sparse &X, int m1, int n1, int m2, int n2); 00178 00187 GF2mat(const GF2mat_sparse &X, const ivec &columns); 00188 00196 GF2mat(const bvec &x, bool is_column = true); 00197 00199 GF2mat(const bmat &X); 00200 00202 void set_size(int m, int n, bool copy = false); 00203 00205 GF2mat_sparse sparsify() const; 00206 00208 bvec bvecify() const; 00209 00210 // ----------- Elementwise manipulation and simple functions ------------- 00211 00213 inline bin get(int i, int j) const; 00214 00216 inline bin operator()(int i, int j) const { return get(i, j); }; 00217 00219 inline void set(int i, int j, bin s); 00220 00222 inline void addto_element(int i, int j, bin s); 00223 00225 void set_col(int j, bvec x); 00226 00228 void set_row(int i, bvec x); 00229 00231 bool is_zero() const; 00232 00234 void swap_rows(int i, int j); 00235 00237 void swap_cols(int i, int j); 00238 00245 void permute_rows(ivec &perm, bool I); 00246 00254 void permute_cols(ivec &perm, bool I); 00255 00257 GF2mat transpose() const; 00258 00260 GF2mat get_submatrix(int m1, int n1, int m2, int n2) const; 00261 00263 GF2mat concatenate_horizontal(const GF2mat &X) const; 00264 00266 GF2mat concatenate_vertical(const GF2mat &X) const; 00267 00269 bvec get_row(int i) const; 00270 00272 bvec get_col(int j) const; 00273 00275 double density() const; 00276 00278 int rows() const { return nrows; } 00279 00281 int cols() const { return ncols; } 00282 00290 void add_rows(int i, int j); 00291 00292 // ---------- Linear algebra -------------- 00293 00299 GF2mat inverse() const; 00300 00302 int row_rank() const; 00303 00320 int T_fact(GF2mat &T, GF2mat &U, ivec &P) const; 00321 00343 int T_fact_update_bitflip(GF2mat &T, GF2mat &U, 00344 ivec &P, int rank, int r, int c) const; 00345 00367 bool T_fact_update_addcol(GF2mat &T, GF2mat &U, 00368 ivec &P, bvec newcol) const; 00369 00370 // ----- Operators ----------- 00371 00373 void operator=(const GF2mat &X); 00374 00376 bool operator==(const GF2mat &X) const; 00377 00378 // ----- Friends ------ 00379 00381 friend GF2mat operator*(const GF2mat &X, const GF2mat &Y); 00382 00384 friend bvec operator*(const GF2mat &X, const bvec &y); 00385 00390 friend GF2mat operator+(const GF2mat &X, const GF2mat &Y); 00391 00393 friend std::ostream &operator<<(std::ostream &os, const GF2mat &X); 00394 00396 friend it_file &operator<<(it_file &f, const GF2mat &X); 00397 00399 friend it_ifile &operator>>(it_ifile &f, GF2mat &X); 00400 00402 friend GF2mat mult_trans(const GF2mat &X, const GF2mat &Y); 00403 00404 private: 00405 int nrows, ncols; // number of rows and columns of matrix 00406 int nwords; // number of bytes used 00407 Mat<unsigned char> data; // data structure 00408 00409 // This value is used to perform division by bit shift and is equal to 00410 // log2(8) 00411 static const unsigned char shift_divisor = 3; 00412 00413 // This value is used as a mask when computing the bit position of the 00414 // division remainder 00415 static const unsigned char rem_mask = (1 << shift_divisor) - 1; 00416 }; 00417 00418 00419 // ---------------------------------------------------------------------- 00420 // GF2mat related functions 00421 // ---------------------------------------------------------------------- 00422 00427 it_file &operator<<(it_file &f, const GF2mat &X); 00428 00433 it_ifile &operator>>(it_ifile &f, GF2mat &X); 00434 00439 GF2mat operator*(const GF2mat &X, const GF2mat &Y); 00440 00445 bvec operator*(const GF2mat &X, const bvec &y); 00446 00451 GF2mat operator+(const GF2mat &X, const GF2mat &Y); 00452 00457 std::ostream &operator<<(std::ostream &os, const GF2mat &X); 00458 00463 GF2mat gf2dense_eye(int m); 00464 00469 GF2mat mult_trans(const GF2mat &X, const GF2mat &Y); 00470 00471 00472 // ---------------------------------------------------------------------- 00473 // Inline implementations 00474 // ---------------------------------------------------------------------- 00475 00476 inline void GF2mat::addto_element(int i, int j, bin s) 00477 { 00478 it_assert_debug(i >= 0 && i < nrows, "GF2mat::addto_element()"); 00479 it_assert_debug(j >= 0 && j < ncols, "GF2mat::addto_element()"); 00480 if (s == 1) 00481 data(i, (j >> shift_divisor)) ^= (1 << (j & rem_mask)); 00482 } 00483 00484 inline bin GF2mat::get(int i, int j) const 00485 { 00486 it_assert_debug(i >= 0 && i < nrows, "GF2mat::get_element()"); 00487 it_assert_debug(j >= 0 && j < ncols, "GF2mat::get_element()"); 00488 return (data(i, (j >> shift_divisor)) >> (j & rem_mask)) & 1; 00489 } 00490 00491 inline void GF2mat::set(int i, int j, bin s) 00492 { 00493 it_assert_debug(i >= 0 && i < nrows, "GF2mat::set_element()"); 00494 it_assert_debug(j >= 0 && j < ncols, "GF2mat::set_element()"); 00495 if (s == 1) // set bit to one 00496 data(i, (j >> shift_divisor)) |= (1 << (j & rem_mask)); 00497 else // set bit to zero 00498 data(i, (j >> shift_divisor)) &= (~(1 << (j & rem_mask))); 00499 } 00500 00501 } // namespace itpp 00502 00503 #endif // #ifndef GF2MAT_H
Generated on Tue Nov 23 08:47:55 2010 for IT++ by Doxygen 1.6.1