IT++ Logo Newcom Logo

itpp::GF2mat Class Reference

Class for dense GF(2) matrices. More...

#include <itpp/base/gf2mat.h>

List of all members.

Public Member Functions

 GF2mat ()
 Default constructor (this gives a 1*1 matrix consisting of a single zero).
 GF2mat (int m, int n)
 Construct an empty (all-zero) m*n matrix.
 GF2mat (const GF2mat_sparse &X)
 Construct a dense GF(2) matrix from a sparse GF(2) matrix.
 GF2mat (const GF2mat_sparse &X, int m1, int n1, int m2, int n2)
 Construct a dense GF(2) matrix from a subset (m1,n1) to (m2,n2) of sparse GF(2) matrix.
 GF2mat (const GF2mat_sparse &X, ivec &columns)
 Construct a dense GF(2) matrix from a subset of columns in sparse GF(2) matrix.
 GF2mat (const bvec &x, bool rc=1)
 Create a dense GF(2) matrix from a single vector.
 GF2mat (const bmat &X)
 Create a dense GF(2) matrix from a bmat.
GF2mat_sparse sparsify ()
 Create a sparse GF(2) matrix from a dense GF(2) matrix.
bvec bvecify ()
 Create a bvec from a GF(2) matrix (must have one column or one row).
bin get (int i, int j) const
 Getting element.
bin operator() (int i, int j) const
 Getting element.
void set (int i, int j, bin s)
 Set element i,j to s (0 or 1).
void addto_element (int i, int j, bin s)
 Add s (0 or 1) to element (i,j).
void set_col (int j, bvec x)
 Set column j to a binary vector x.
void set_row (int i, bvec x)
 Set row i to a binary vector x.
bool is_zero ()
 Check whether the matrix is identical to zero.
void swap_rows (int i, int j)
 Swap rows i and j.
void swap_cols (int i, int j)
 Swap columns i and j.
void permute_rows (ivec &perm, bool I)
 Multiply from left with permutation matrix (permute rows).
void permute_cols (ivec &perm, bool I)
 Multiply a matrix from right with a permutation matrix (i.e., permute the columns).
GF2mat transpose () const
 Transpose.
GF2mat get_submatrix (int m1, int n1, int m2, int n2)
 Submatrix from (m1,n1) to (m2,n2).
GF2mat concatenate_horizontal (const GF2mat &X)
 Concatenate horizontally (append X on the right side of matrix).
GF2mat concatenate_vertical (const GF2mat &X)
 Concatenate vertically (append X underneath).
bvec get_row (int i)
 Get row.
bvec get_col (int j)
 Get column.
double density () const
 Compute the matrix density (fraction of elements equal to "1").
int rows ()
 Get number of rows.
int cols ()
 Get number of columns.
void add_rows (int i, int j)
 Add (or equivalently, subtract) row j to row i.
GF2mat inverse ()
 Inversion.
int row_rank ()
 Returns the number of linearly independent rows.
int T_fact (GF2mat &T, GF2mat &U, ivec &P)
 TXP factorization.
int T_fact_update_bitflip (GF2mat &T, GF2mat &U, ivec &P, int rank, int r, int c)
 TXP factorization update, when bit is flipped.
int T_fact_update_addcol (GF2mat &T, GF2mat &U, ivec &P, bvec newcol)
 TXP factorization update, when column is added.
void operator= (const GF2mat &X)
 Assignment operator.
bool operator== (const GF2mat &X) const
 Check if equal.

Friends

GF2mat operator * (const GF2mat &X, const GF2mat &Y)
 GF(2) matrix multiplication.
bvec operator * (const GF2mat &X, const bvec &y)
 GF(2) matrix multiplication with "regular" binary vector.
GF2mat operator+ (const GF2mat &X, const GF2mat &Y)
 GF(2) matrix addition.
std::ostream & operator<< (std::ostream &os, const GF2mat &X)
 Output stream (plain text) operator for dense GF(2) matrices.
it_fileoperator<< (it_file &f, const GF2mat &X)
 Write the matrix to file.
it_ifileoperator>> (it_ifile &f, GF2mat &X)
 Read the matrix from file.
GF2mat mult_trans (const GF2mat &X, const GF2mat &Y)
 Multiplication X*Y' where X and Y are GF(2) matrices.

Related Functions

(Note that these are not member functions.)

GF2mat gf2dense_eye (int m)
 GF(2) Identity matrix.


Detailed Description

Class for dense GF(2) matrices.

This class is used to represent relatively large GF(2) matrices making efficient use of computer memory. (One bit in the matrix requires one bit of memory.)

The GF2mat class extends the bmat class by offering a more memory efficient representation of data and providing several functios for linear algebra. GF2mat may be used in lieu of bmat whenever the linear algebra functionality or improved memory efficiency is desired.

See also GF2mat_sparse which offers an efficient representation of sparse GF(2) matrices.

Definition at line 116 of file gf2mat.h.


Constructor & Destructor Documentation

itpp::GF2mat::GF2mat (  ) 

Default constructor (this gives a 1*1 matrix consisting of a single zero).

Definition at line 54 of file gf2mat.cpp.

References itpp::Mat< Num_T >::set_size().

Referenced by itpp::operator *(), and T_fact_update_addcol().

itpp::GF2mat::GF2mat ( int  m,
int  n 
)

Construct an empty (all-zero) m*n matrix.

Definition at line 40 of file gf2mat.cpp.

References lImax, and itpp::Mat< Num_T >::set_size().

itpp::GF2mat::GF2mat ( const GF2mat_sparse X  ) 

Construct a dense GF(2) matrix from a sparse GF(2) matrix.

Definition at line 95 of file gf2mat.cpp.

References itpp::Sparse_Mat< T >::cols(), itpp::Sparse_Mat< T >::get_col(), lImax, itpp::Sparse_Mat< T >::rows(), and itpp::Mat< Num_T >::set_size().

itpp::GF2mat::GF2mat ( const GF2mat_sparse X,
int  m1,
int  n1,
int  m2,
int  n2 
)

Construct a dense GF(2) matrix from a subset (m1,n1) to (m2,n2) of sparse GF(2) matrix.

Definition at line 117 of file gf2mat.cpp.

References itpp::Sparse_Mat< T >::cols(), it_assert1, lImax, itpp::Sparse_Mat< T >::rows(), and itpp::Mat< Num_T >::set_size().

itpp::GF2mat::GF2mat ( const GF2mat_sparse X,
ivec &  columns 
)

Construct a dense GF(2) matrix from a subset of columns in sparse GF(2) matrix.

Definition at line 143 of file gf2mat.cpp.

References itpp::Sparse_Mat< T >::cols(), itpp::Sparse_Mat< T >::get_col(), it_assert1, itpp::length(), lImax, itpp::max(), itpp::min(), itpp::Sparse_Mat< T >::rows(), and itpp::Mat< Num_T >::set_size().

itpp::GF2mat::GF2mat ( const bvec &  x,
bool  rc = 1 
)

Create a dense GF(2) matrix from a single vector.

Parameters:
x The input vector
rc A parameter that indicates whether the result should be a row vector (rc=0), or a column vector (rc=1, default)

Definition at line 63 of file gf2mat.cpp.

References itpp::length(), lImax, and itpp::Mat< Num_T >::set_size().

itpp::GF2mat::GF2mat ( const bmat X  ) 

Create a dense GF(2) matrix from a bmat.

Definition at line 89 of file gf2mat.cpp.

References it_error.


Member Function Documentation

GF2mat_sparse itpp::GF2mat::sparsify (  ) 

Create a sparse GF(2) matrix from a dense GF(2) matrix.

Definition at line 167 of file gf2mat.cpp.

References itpp::Sparse_Mat< T >::set().

bvec itpp::GF2mat::bvecify (  ) 

Create a bvec from a GF(2) matrix (must have one column or one row).

Definition at line 181 of file gf2mat.cpp.

References it_assert1.

bin itpp::GF2mat::get ( int  i,
int  j 
) const [inline]

Getting element.

Definition at line 400 of file gf2mat.h.

References it_assert0, lImax, and mImax.

Referenced by concatenate_horizontal(), inverse(), itpp::operator<<(), T_fact(), T_fact_update_addcol(), and T_fact_update_bitflip().

bin itpp::GF2mat::operator() ( int  i,
int  j 
) const [inline]

Getting element.

Definition at line 161 of file gf2mat.h.

void itpp::GF2mat::set ( int  i,
int  j,
bin  s 
) [inline]

Set element i,j to s (0 or 1).

Definition at line 409 of file gf2mat.h.

References it_assert0, lImax, and mImax.

Referenced by concatenate_horizontal(), get_submatrix(), itpp::gf2dense_eye(), itpp::mult_trans(), and transpose().

void itpp::GF2mat::addto_element ( int  i,
int  j,
bin  s 
) [inline]

Add s (0 or 1) to element (i,j).

Definition at line 389 of file gf2mat.h.

References it_assert0, lImax, and mImax.

Referenced by T_fact_update_bitflip().

void itpp::GF2mat::set_col ( int  j,
bvec  x 
)

Set column j to a binary vector x.

Definition at line 201 of file gf2mat.cpp.

References it_assert1, and itpp::length().

Referenced by permute_cols(), swap_cols(), and T_fact_update_bitflip().

void itpp::GF2mat::set_row ( int  i,
bvec  x 
)

Set row i to a binary vector x.

Definition at line 193 of file gf2mat.cpp.

References it_assert1, and itpp::length().

Referenced by T_fact_update_bitflip().

bool itpp::GF2mat::is_zero (  ) 

Check whether the matrix is identical to zero.

Definition at line 509 of file gf2mat.cpp.

void itpp::GF2mat::swap_rows ( int  i,
int  j 
)

Swap rows i and j.

Definition at line 548 of file gf2mat.cpp.

References it_assert0.

Referenced by T_fact(), T_fact_update_addcol(), and T_fact_update_bitflip().

void itpp::GF2mat::swap_cols ( int  i,
int  j 
)

Swap columns i and j.

Definition at line 559 of file gf2mat.cpp.

References get_col(), it_assert0, and set_col().

Referenced by T_fact(), and T_fact_update_bitflip().

void itpp::GF2mat::permute_rows ( ivec &  perm,
bool  I 
)

Multiply from left with permutation matrix (permute rows).

Parameters:
perm Permutation vector
I Parameter that determines permutation. I=0: apply permutation, I=1: apply inverse permutation

Definition at line 709 of file gf2mat.cpp.

References data, it_assert1, and itpp::length().

Referenced by inverse().

void itpp::GF2mat::permute_cols ( ivec &  perm,
bool  I 
)

Multiply a matrix from right with a permutation matrix (i.e., permute the columns).

Parameters:
I Parameter that determines permutation. I=0: apply permutation, I=1: apply inverse permutation

Definition at line 695 of file gf2mat.cpp.

References get_col(), it_assert1, itpp::length(), and set_col().

GF2mat itpp::GF2mat::transpose (  )  const

Transpose.

Definition at line 666 of file gf2mat.cpp.

References set().

Referenced by itpp::operator *().

GF2mat itpp::GF2mat::get_submatrix ( int  m1,
int  n1,
int  m2,
int  n2 
)

Submatrix from (m1,n1) to (m2,n2).

Definition at line 219 of file gf2mat.cpp.

References it_assert1, and set().

GF2mat itpp::GF2mat::concatenate_horizontal ( const GF2mat X  ) 

Concatenate horizontally (append X on the right side of matrix).

Definition at line 255 of file gf2mat.cpp.

References get(), it_assert1, ncols, nrows, and set().

Referenced by T_fact_update_addcol().

GF2mat itpp::GF2mat::concatenate_vertical ( const GF2mat X  ) 

Concatenate vertically (append X underneath).

Definition at line 234 of file gf2mat.cpp.

References data, it_assert1, ncols, nrows, and nwords.

bvec itpp::GF2mat::get_row ( int  i  ) 

Get row.

Definition at line 277 of file gf2mat.cpp.

References itpp::zeros_b().

Referenced by T_fact_update_bitflip().

bvec itpp::GF2mat::get_col ( int  j  ) 

Get column.

Definition at line 287 of file gf2mat.cpp.

References itpp::zeros_b().

Referenced by permute_cols(), swap_cols(), and T_fact_update_bitflip().

double itpp::GF2mat::density (  )  const

Compute the matrix density (fraction of elements equal to "1").

Definition at line 747 of file gf2mat.cpp.

Referenced by itpp::operator<<().

int itpp::GF2mat::rows (  )  [inline]

Get number of rows.

Definition at line 221 of file gf2mat.h.

Referenced by T_fact_update_addcol().

int itpp::GF2mat::cols (  )  [inline]

Get number of columns.

Definition at line 224 of file gf2mat.h.

Referenced by T_fact_update_addcol().

void itpp::GF2mat::add_rows ( int  i,
int  j 
)

Add (or equivalently, subtract) row j to row i.

Definition at line 539 of file gf2mat.cpp.

References it_assert0.

Referenced by inverse(), T_fact(), T_fact_update_addcol(), and T_fact_update_bitflip().

GF2mat itpp::GF2mat::inverse (  ) 

Inversion.

The matrix must be invertible, otherwise the function will terminate with an error.

Definition at line 478 of file gf2mat.cpp.

References add_rows(), get(), it_assert1, permute_rows(), and T_fact().

int itpp::GF2mat::row_rank (  ) 

Returns the number of linearly independent rows.

Definition at line 501 of file gf2mat.cpp.

References T_fact().

Referenced by T_fact_update_addcol().

int itpp::GF2mat::T_fact ( GF2mat T,
GF2mat U,
ivec &  P 
)

TXP factorization.

Given X, compute a factorization of the form U=TXP, where U is upper triangular, T is square and invertible, and P is a permutation matrix. This is basically an "LU"-factorization, but not called so here because T is not necessarily lower trianglular. The matrix X may have any dimension. The permutation matrix P is represented as a permutation vector.

The function returns the row rank of X. (If X is full row rank, then the number of rows is returned.)

Definition at line 298 of file gf2mat.cpp.

References add_rows(), itpp::floor_i(), get(), gf2dense_eye(), swap_cols(), swap_rows(), and itpp::zeros_i().

Referenced by inverse(), and row_rank().

int itpp::GF2mat::T_fact_update_bitflip ( GF2mat T,
GF2mat U,
ivec &  P,
int  rank,
int  r,
int  c 
)

TXP factorization update, when bit is flipped.

Update upper triangular factor U in the T-factorization (U=TXP) when the bit at position (r,c) is changed (0->1 or 1->0). The purpose of this function is to avoid re-running a complete T-factorization when a single bit is changed. The function assumes that T, U, and P already exist and that U=TXP before the function is called. The function also assumes that the rank provided is correct. The function updates T, U and P these matrices. The function returns the new rank of the matrix after the bitflip.

Note: T, U, P and the rank value supplied to the function must be correct one. This is not checked by the function (for reasons of efficiency).

This function was primarily written specifically for use by certain optimization algorithms in the LDPC codec class.

Definition at line 353 of file gf2mat.cpp.

References add_rows(), addto_element(), get(), get_col(), get_row(), it_error, set_col(), set_row(), swap_cols(), and swap_rows().

int itpp::GF2mat::T_fact_update_addcol ( GF2mat T,
GF2mat U,
ivec &  P,
bvec  newcol 
)

TXP factorization update, when column is added.

Update upper triangular factor U in the T-factorization (U=TXP) when a column (newcol) is appended at the right side of the matrix. The purpose of this function is to avoid re-running a complete T-factorization when a column is added. The function ONLY adds the column if it improves the rank of the matrix (nothing is done otherwise). The function returns 1 if the column was added, and 0 otherwise.

Note: T, U, P and the rank value supplied to the function must be correct one. This is not checked by the function (for reasons of efficiency). Also, the matrix operating on must have full column rank (this is assumed by the function, but not checked for reasons of efficiency).

This function was written primarily intended for use by the LDPC codec class.

Definition at line 434 of file gf2mat.cpp.

References add_rows(), cols(), concatenate_horizontal(), get(), GF2mat(), it_assert0, it_assert1, itpp::length(), row_rank(), rows(), and swap_rows().

void itpp::GF2mat::operator= ( const GF2mat X  ) 

Assignment operator.

Definition at line 569 of file gf2mat.cpp.

References data, ncols, nrows, and nwords.

bool itpp::GF2mat::operator== ( const GF2mat X  )  const

Check if equal.

Definition at line 521 of file gf2mat.cpp.

References data, it_assert1, ncols, nrows, and nwords.


Friends And Related Function Documentation

GF2mat operator * ( const GF2mat X,
const GF2mat Y 
) [friend]

GF(2) matrix multiplication.

Definition at line 577 of file gf2mat.cpp.

bvec operator * ( const GF2mat X,
const bvec &  y 
) [friend]

GF(2) matrix multiplication with "regular" binary vector.

Definition at line 603 of file gf2mat.cpp.

GF2mat operator+ ( const GF2mat X,
const GF2mat Y 
) [friend]

GF(2) matrix addition.

Subtraction is not implemented because it is equivalent to addition.

Definition at line 679 of file gf2mat.cpp.

std::ostream & operator<< ( std::ostream &  os,
const GF2mat X 
) [friend]

Output stream (plain text) operator for dense GF(2) matrices.

Definition at line 730 of file gf2mat.cpp.

it_file& operator<< ( it_file f,
const GF2mat X 
) [friend]

Write the matrix to file.

/relates GF2mat /brief Write GF(2) matrix to file.

Definition at line 761 of file gf2mat.cpp.

it_ifile& operator>> ( it_ifile f,
GF2mat X 
) [friend]

Read the matrix from file.

/relates GF2mat /brief Read GF(2) matrix from file.

Definition at line 778 of file gf2mat.cpp.

GF2mat mult_trans ( const GF2mat X,
const GF2mat Y 
) [friend]

Multiplication X*Y' where X and Y are GF(2) matrices.

Definition at line 633 of file gf2mat.cpp.

Referenced by itpp::operator *().

GF2mat gf2dense_eye ( int  m  )  [related]

GF(2) Identity matrix.

Definition at line 210 of file gf2mat.cpp.

Referenced by T_fact().


The documentation for this class was generated from the following files:
SourceForge Logo

Generated on Wed Apr 18 11:20:03 2007 for IT++ by Doxygen 1.5.2