gf2mat.h
Go to the documentation of this file.
#ifndef GF2MAT_H
#define GF2MAT_H
#include <itpp/base/vec.h>
#include <itpp/base/mat.h>
#include <itpp/base/svec.h>
#include <itpp/base/smat.h>
#include <itpp/base/itfile.h>
#include <itpp/itexports.h>
namespace itpp
{
#if (defined(_MSC_VER) && defined(ITPP_SHARED_LIB))
//MSVC needs to explicitely instantiate required templates while building the
//shared library. Also, these definitions are marked as imported when library is
//linked with user's code.
template class ITPP_EXPORT Sparse_Mat<bin>;
template class ITPP_EXPORT Sparse_Vec<bin>;
template class ITPP_EXPORT Mat<unsigned char>;
#endif
// ----------------------------------------------------------------------
// Sparse GF(2) matrix class
// ----------------------------------------------------------------------
typedef Sparse_Vec<bin> GF2vec_sparse;
typedef Sparse_Mat<bin> GF2mat_sparse;
// ----------------------------------------------------------------------
// Alist parameterization of sparse GF(2) matrix class
// ----------------------------------------------------------------------
class ITPP_EXPORT GF2mat_sparse_alist
{
public:
GF2mat_sparse_alist() : data_ok(false) {}
GF2mat_sparse_alist(const std::string &fname);
void read(const std::string &fname);
void write(const std::string &fname) const;
GF2mat_sparse to_sparse(bool transpose = false) const;
void from_sparse(const GF2mat_sparse &mat, bool transpose = false);
protected:
bool data_ok;
int M;
int N;
imat mlist;
imat nlist;
ivec num_mlist;
ivec num_nlist;
int max_num_m;
int max_num_n;
};
// ----------------------------------------------------------------------
// Dense GF(2) matrix class
// ----------------------------------------------------------------------
class ITPP_EXPORT GF2mat
{
public:
// ----------- Constructors -----------
GF2mat();
GF2mat(int m, int n);
GF2mat(const GF2mat_sparse &X);
GF2mat(const GF2mat_sparse &X, int m1, int n1, int m2, int n2);
GF2mat(const GF2mat_sparse &X, const ivec &columns);
GF2mat(const bvec &x, bool is_column = true);
GF2mat(const bmat &X);
void set_size(int m, int n, bool copy = false);
GF2mat_sparse sparsify() const;
bvec bvecify() const;
// ----------- Elementwise manipulation and simple functions -------------
inline bin get(int i, int j) const;
inline bin operator()(int i, int j) const { return get(i, j); };
inline void set(int i, int j, bin s);
inline void addto_element(int i, int j, bin s);
void set_col(int j, bvec x);
void set_row(int i, bvec x);
bool is_zero() const;
void swap_rows(int i, int j);
void swap_cols(int i, int j);
void permute_rows(ivec &perm, bool I);
void permute_cols(ivec &perm, bool I);
GF2mat transpose() const;
GF2mat get_submatrix(int m1, int n1, int m2, int n2) const;
GF2mat concatenate_horizontal(const GF2mat &X) const;
GF2mat concatenate_vertical(const GF2mat &X) const;
bvec get_row(int i) const;
bvec get_col(int j) const;
double density() const;
int rows() const { return nrows; }
int cols() const { return ncols; }
void add_rows(int i, int j);
// ---------- Linear algebra --------------
GF2mat inverse() const;
int row_rank() const;
int T_fact(GF2mat &T, GF2mat &U, ivec &P) const;
int T_fact_update_bitflip(GF2mat &T, GF2mat &U,
ivec &P, int rank, int r, int c) const;
bool T_fact_update_addcol(GF2mat &T, GF2mat &U,
ivec &P, bvec newcol) const;
// ----- Operators -----------
void operator=(const GF2mat &X);
bool operator==(const GF2mat &X) const;
// ----- Friends ------
friend ITPP_EXPORT GF2mat operator*(const GF2mat &X, const GF2mat &Y);
friend ITPP_EXPORT bvec operator*(const GF2mat &X, const bvec &y);
friend ITPP_EXPORT GF2mat operator+(const GF2mat &X, const GF2mat &Y);
friend ITPP_EXPORT std::ostream &operator<<(std::ostream &os, const GF2mat &X);
friend ITPP_EXPORT it_file &operator<<(it_file &f, const GF2mat &X);
friend ITPP_EXPORT it_ifile &operator>>(it_ifile &f, GF2mat &X);
friend ITPP_EXPORT GF2mat mult_trans(const GF2mat &X, const GF2mat &Y);
private:
int nrows, ncols; // number of rows and columns of matrix
int nwords; // number of bytes used
Mat<unsigned char> data; // data structure
// This value is used to perform division by bit shift and is equal to
// log2(8)
static const unsigned char shift_divisor = 3;
// This value is used as a mask when computing the bit position of the
// division remainder
static const unsigned char rem_mask = (1 << shift_divisor) - 1;
};
// ----------------------------------------------------------------------
// GF2mat related functions
// ----------------------------------------------------------------------
ITPP_EXPORT it_file &operator<<(it_file &f, const GF2mat &X);
ITPP_EXPORT it_ifile &operator>>(it_ifile &f, GF2mat &X);
ITPP_EXPORT GF2mat operator*(const GF2mat &X, const GF2mat &Y);
ITPP_EXPORT bvec operator*(const GF2mat &X, const bvec &y);
ITPP_EXPORT GF2mat operator+(const GF2mat &X, const GF2mat &Y);
ITPP_EXPORT std::ostream &operator<<(std::ostream &os, const GF2mat &X);
ITPP_EXPORT GF2mat gf2dense_eye(int m);
ITPP_EXPORT GF2mat mult_trans(const GF2mat &X, const GF2mat &Y);
// ----------------------------------------------------------------------
// Inline implementations
// ----------------------------------------------------------------------
inline void GF2mat::addto_element(int i, int j, bin s)
{
it_assert_debug(i >= 0 && i < nrows, "GF2mat::addto_element()");
it_assert_debug(j >= 0 && j < ncols, "GF2mat::addto_element()");
if (s == 1)
data(i, (j >> shift_divisor)) ^= (1 << (j & rem_mask));
}
inline bin GF2mat::get(int i, int j) const
{
it_assert_debug(i >= 0 && i < nrows, "GF2mat::get_element()");
it_assert_debug(j >= 0 && j < ncols, "GF2mat::get_element()");
return (data(i, (j >> shift_divisor)) >> (j & rem_mask)) & 1;
}
inline void GF2mat::set(int i, int j, bin s)
{
it_assert_debug(i >= 0 && i < nrows, "GF2mat::set_element()");
it_assert_debug(j >= 0 && j < ncols, "GF2mat::set_element()");
if (s == 1) // set bit to one
data(i, (j >> shift_divisor)) |= (1 << (j & rem_mask));
else // set bit to zero
data(i, (j >> shift_divisor)) &= (~(1 << (j & rem_mask)));
}
} // namespace itpp
#endif // #ifndef GF2MAT_H
itpp::rank
int rank(const Mat< T > &m, double tol=-1.0)
Calculate the rank of matrix m.
Definition: matfunc.h:493
itpp::GF2mat_sparse_alist::num_nlist
ivec num_nlist
Weight of each column n.
Definition: gf2mat.h:142
itpp::GF2mat_sparse_alist::max_num_m
int max_num_m
Maximum weight of rows.
Definition: gf2mat.h:144
itpp::GF2mat_sparse_alist::num_mlist
ivec num_mlist
Weight of each row m.
Definition: gf2mat.h:140
itpp::GF2mat::set
void set(int i, int j, bin s)
Set element i,j to s (0 or 1)
Definition: gf2mat.h:505
itfile.h
Definition of classes for the IT++ file format.
itpp::GF2mat
Class for dense GF(2) matrices.
Definition: gf2mat.h:171
itpp::GF2mat::rows
int rows() const
Get number of rows.
Definition: gf2mat.h:291
itpp::GF2mat::get
bin get(int i, int j) const
Getting element.
Definition: gf2mat.h:498
itpp::mult_trans
GF2mat mult_trans(const GF2mat &X, const GF2mat &Y)
Multiplication X*Y&#39; where X and Y are GF(2) matrices.
Definition: gf2mat.cpp:903
itpp::GF2mat_sparse_alist::nlist
imat nlist
List of integer coordinates in the n direction with non-zero entries.
Definition: gf2mat.h:138
itpp::operator<<
std::ostream & operator<<(std::ostream &output, const bin &inbin)
Output stream of bin.
Definition: binary.cpp:36
itpp::GF2mat_sparse_alist::data_ok
bool data_ok
Flag indicating that "alist" matrix data are properly set.
Definition: gf2mat.h:130
itpp::gf2dense_eye
GF2mat gf2dense_eye(int m)
GF(2) Identity matrix.
Definition: gf2mat.cpp:470
it_assert_debug
#define it_assert_debug(t, s)
Abort if t is not true and NDEBUG is not defined.
Definition: itassert.h:107
smat.h
Sparse Matrix Class Definitions.
itpp::GF2mat_sparse_alist::M
int M
Size of the matrix: M rows x N columns.
Definition: gf2mat.h:132
mat.h
Matrix Class Definitions.
itpp::GF2mat::cols
int cols() const
Get number of columns.
Definition: gf2mat.h:294
itpp::operator+
GF2mat operator+(const GF2mat &X, const GF2mat &Y)
GF(2) matrix addition.
Definition: gf2mat.cpp:948
itpp::it_file
The IT++ file format reading and writing class.
Definition: itfile.h:245
itpp::GF2mat_sparse_alist::mlist
imat mlist
List of integer coordinates in the m direction with non-zero entries.
Definition: gf2mat.h:136
itpp::it_ifile
The IT++ file format reading class.
Definition: itfile.h:132
itpp
itpp namespace
Definition: itmex.h:36
itpp::operator*
GF2mat operator*(const GF2mat &X, const GF2mat &Y)
GF(2) matrix multiplication.
Definition: gf2mat.cpp:847
itpp::GF2mat_sparse
Sparse_Mat< bin > GF2mat_sparse
Sparse GF(2) matrix.
Definition: gf2mat.h:77
itpp::bin
Binary arithmetic (boolean) class.
Definition: binary.h:56
itpp::transpose
void transpose(const Mat< T > &m, Mat< T > &out)
Transposition of the matrix m returning the transposed matrix in out.
Definition: matfunc.h:308
itpp::GF2mat::addto_element
void addto_element(int i, int j, bin s)
Add s (0 or 1) to element (i,j)
Definition: gf2mat.h:490
itpp::GF2mat_sparse_alist::N
int N
Size of the matrix: M rows x N columns.
Definition: gf2mat.h:134
itpp::GF2mat_sparse_alist::GF2mat_sparse_alist
GF2mat_sparse_alist()
Default constructor.
Definition: gf2mat.h:102
itpp::GF2vec_sparse
Sparse_Vec< bin > GF2vec_sparse
Sparse GF(2) vector.
Definition: gf2mat.h:74
svec.h
Sparse Vector Class definitions.
itpp::operator>>
std::istream & operator>>(std::istream &input, bin &outbin)
Input stream of bin.
Definition: binary.cpp:42
itpp::GF2mat_sparse_alist
Parameterized "alist" representation of sparse GF(2) matrix.
Definition: gf2mat.h:98
itpp::GF2mat_sparse_alist::max_num_n
int max_num_n
Maximum weight of columns.
Definition: gf2mat.h:146
itpp::GF2mat::operator()
bin operator()(int i, int j) const
Getting element.
Definition: gf2mat.h:229
bmat
Mat< bin > bmat
bin matrix
Definition: mat.h:508
vec.h
Templated Vector Class Definitions.

Generated on Sat Sep 30 2017 07:04:09 for IT++ by Doxygen 1.8.13