IT++ Logo

gf2mat.h

Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
SourceForge Logo

Generated on Sun Dec 20 07:05:37 2009 for IT++ by Doxygen 1.6.1