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   // 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   public:
00087     GF2mat_sparse_alist() : data_ok(false) {}
00089     GF2mat_sparse_alist(const std::string &fname);
00090 
00092     void read(const std::string &fname);
00094     void write(const std::string &fname) const;
00095 
00102     GF2mat_sparse to_sparse(bool transpose = false) const;
00103 
00111     void from_sparse(const GF2mat_sparse &mat, bool transpose = false);
00112 
00113   protected:
00115     bool data_ok;
00117     int M;
00119     int N;
00121     imat mlist;
00123     imat nlist;
00125     ivec num_mlist;
00127     ivec num_nlist;
00129     int max_num_m;
00131     int max_num_n;
00132   };
00133 
00134 
00135   // ----------------------------------------------------------------------
00136   // Dense GF(2) matrix class
00137   // ----------------------------------------------------------------------
00138 
00156   class GF2mat {
00157   public:
00158 
00159     // ----------- Constructors -----------
00160 
00162     GF2mat();
00163 
00165     GF2mat(int m, int n);
00166 
00168     GF2mat(const GF2mat_sparse &X);
00169 
00174     GF2mat(const GF2mat_sparse &X, int m1, int n1, int m2, int n2);
00175 
00184     GF2mat(const GF2mat_sparse &X, const ivec &columns);
00185 
00193     GF2mat(const bvec &x, bool is_column = true);
00194 
00196     GF2mat(const bmat &X);
00197 
00199     void set_size(int m, int n, bool copy = false);
00200 
00202     GF2mat_sparse sparsify() const;
00203 
00205     bvec bvecify() const;
00206 
00207     // ----------- Elementwise manipulation and simple functions -------------
00208 
00210     inline bin get(int i, int j) const;
00211 
00213     inline bin operator()(int i, int j) const { return get(i,j); };
00214 
00216     inline void set(int i, int j, bin s);
00217 
00219     inline void addto_element(int i, int j, bin s);
00220 
00222     void set_col(int j, bvec x);
00223 
00225     void set_row(int i, bvec x);
00226 
00228     bool is_zero() const;
00229 
00231     void swap_rows(int i, int j);
00232 
00234     void swap_cols(int i, int j);
00235 
00242     void permute_rows(ivec &perm, bool I);
00243 
00251     void permute_cols(ivec &perm, bool I);
00252 
00254     GF2mat transpose() const;
00255 
00257     GF2mat get_submatrix(int m1, int n1, int m2, int n2) const;
00258 
00260     GF2mat concatenate_horizontal(const GF2mat &X) const;
00261 
00263     GF2mat concatenate_vertical(const GF2mat &X) const;
00264 
00266     bvec get_row(int i) const;
00267 
00269     bvec get_col(int j) const;
00270 
00272     double density() const;
00273 
00275     int rows() const { return nrows; }
00276 
00278     int cols() const { return ncols; }
00279 
00287     void add_rows(int i, int j);
00288 
00289     // ---------- Linear algebra --------------
00290 
00296     GF2mat inverse() const;
00297 
00299     int row_rank() const;
00300 
00317     int T_fact(GF2mat &T, GF2mat &U, ivec &P) const;
00318 
00340     int T_fact_update_bitflip(GF2mat &T, GF2mat &U,
00341                               ivec &P, int rank, int r, int c) const;
00342 
00364     bool T_fact_update_addcol(GF2mat &T, GF2mat &U,
00365                               ivec &P, bvec newcol) const;
00366 
00367     // ----- Operators -----------
00368 
00370     void operator=(const GF2mat &X);
00371 
00373     bool operator==(const GF2mat &X) const;
00374 
00375     // ----- Friends ------
00376 
00378     friend GF2mat operator*(const GF2mat &X, const GF2mat &Y);
00379 
00381     friend bvec operator*(const GF2mat &X, const bvec &y);
00382 
00387     friend GF2mat operator+(const GF2mat &X, const GF2mat &Y);
00388 
00390     friend std::ostream &operator<<(std::ostream &os, const GF2mat &X);
00391 
00393     friend it_file &operator<<(it_file &f, const GF2mat &X);
00394 
00396     friend it_ifile &operator>>(it_ifile &f, GF2mat &X);
00397 
00399     friend GF2mat mult_trans(const GF2mat &X, const GF2mat &Y);
00400 
00401   private:
00402     int nrows, ncols;            // number of rows and columns of matrix
00403     int nwords;                  // number of bytes used
00404     Mat<unsigned char> data;             // data structure
00405 
00406     // This value is used to perform division by bit shift and is equal to
00407     // log2(8)
00408     static const unsigned char shift_divisor = 3;
00409 
00410     // This value is used as a mask when computing the bit position of the
00411     // division remainder
00412     static const unsigned char rem_mask = (1 << shift_divisor) - 1;
00413   };
00414 
00415 
00416   // ----------------------------------------------------------------------
00417   // GF2mat related functions
00418   // ----------------------------------------------------------------------
00419 
00424   it_file &operator<<(it_file &f, const GF2mat &X);
00425 
00430   it_ifile &operator>>(it_ifile &f, GF2mat &X);
00431 
00436   GF2mat operator*(const GF2mat &X, const GF2mat &Y);
00437 
00442   bvec operator*(const GF2mat &X, const bvec &y);
00443 
00448   GF2mat operator+(const GF2mat &X, const GF2mat &Y);
00449 
00454   std::ostream &operator<<(std::ostream &os, const GF2mat &X);
00455 
00460   GF2mat gf2dense_eye(int m);
00461 
00466   GF2mat mult_trans(const GF2mat &X, const GF2mat &Y);
00467 
00468 
00469   // ----------------------------------------------------------------------
00470   // Inline implementations
00471   // ----------------------------------------------------------------------
00472 
00473   inline void GF2mat::addto_element(int i, int j, bin s)
00474   {
00475     it_assert_debug(i >= 0 && i < nrows, "GF2mat::addto_element()");
00476     it_assert_debug(j >= 0 && j < ncols, "GF2mat::addto_element()");
00477     if (s == 1)
00478       data(i, (j >> shift_divisor)) ^= (1 << (j & rem_mask));
00479   }
00480 
00481   inline bin GF2mat::get(int i, int j) const
00482   {
00483     it_assert_debug(i >= 0 && i < nrows, "GF2mat::get_element()");
00484     it_assert_debug(j >= 0 && j < ncols, "GF2mat::get_element()");
00485     return (data(i, (j >> shift_divisor)) >> (j & rem_mask)) & 1;
00486   }
00487 
00488   inline void GF2mat::set(int i, int j, bin s)
00489   {
00490     it_assert_debug(i >= 0 && i < nrows, "GF2mat::set_element()");
00491     it_assert_debug(j >= 0 && j < ncols, "GF2mat::set_element()");
00492     if (s == 1) // set bit to one
00493       data(i, (j >> shift_divisor)) |= (1 << (j & rem_mask));
00494     else // set bit to zero
00495       data(i, (j >> shift_divisor)) &= (~(1 << (j & rem_mask)));
00496   }
00497 
00498 } // namespace itpp
00499 
00500 #endif // #ifndef GF2MAT_H
SourceForge Logo

Generated on Sat Apr 19 10:42:04 2008 for IT++ by Doxygen 1.5.5