itpp::GF2mat Class Reference

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

#include <gf2mat.h>

List of all members.

Public Member Functions
	GF2mat ()
	Default constructor (gives an empty 1 x 1 matrix).
	GF2mat (int m, int n)
	Construct an empty (all-zero) m x 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)
	Constructor, from subset of sparse GF(2) matrix.
	GF2mat (const GF2mat_sparse &X, const ivec &columns)
	Constructor, from subset of sparse GF(2) matrix.
	GF2mat (const bvec &x, bool is_column=true)
	Create a dense GF(2) matrix from a single vector.
	GF2mat (const bmat &X)
	Create a dense GF(2) matrix from a bmat.
void	set_size (int m, int n, bool copy=false)
	Set size of GF(2) matrix. If copy = true, keep data before resizing.
GF2mat_sparse	sparsify () const
	Create a sparse GF(2) matrix from a dense GF(2) matrix.
bvec	bvecify () const
	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 () const
	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) const
	Submatrix from (m1,n1) to (m2,n2).
GF2mat	concatenate_horizontal (const GF2mat &X) const
	Concatenate horizontally (append X on the right side of matrix).
GF2mat	concatenate_vertical (const GF2mat &X) const
	Concatenate vertically (append X underneath).
bvec	get_row (int i) const
	Get row.
bvec	get_col (int j) const
	Get column.
double	density () const
	Compute the matrix density (fraction of elements equal to "1").
int	rows () const
	Get number of rows.
int	cols () const
	Get number of columns.
void	add_rows (int i, int j)
	Add (or equivalently, subtract) rows.
GF2mat	inverse () const
	Inversion.
int	row_rank () const
	Returns the number of linearly independent rows.
int	T_fact (GF2mat &T, GF2mat &U, ivec &P) const
	TXP factorization.
int	T_fact_update_bitflip (GF2mat &T, GF2mat &U, ivec &P, int rank, int r, int c) const
	TXP factorization update, when bit is flipped.
bool	T_fact_update_addcol (GF2mat &T, GF2mat &U, ivec &P, bvec newcol) const
	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)
	Multiplication operator.
bvec	operator* (const GF2mat &X, const bvec &y)
	Multiplication operator with binary vector.
GF2mat	operator+ (const GF2mat &X, const GF2mat &Y)
	Addition operator.
std::ostream &	operator<< (std::ostream &os, const GF2mat &X)
	Output stream operator (plain text).
it_file &	operator<< (it_file &f, const GF2mat &X)
	Write the matrix to file.
it_ifile &	operator>> (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.

Author:

Erik G. Larsson

This class can be used as an alternative to bmat to represent GF(2) matrices. It extends the functionality of bmat in two ways:

• GF2mat makes more efficient use of computer memory than bmat (one bit in the matrix requires one bit of memory)
• GF2mat provides several functions for linear algebra and matrix factorizations

See also GF2mat_sparse which offers an efficient representation of sparse GF(2) matrices, and GF2mat_sparse_alist for a parameterized representation of sparse GF(2) matrices.

---

Constructor & Destructor Documentation

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

Constructor, from subset of sparse GF(2) matrix.

This constructor forms a dense GF(2) matrix from a subset (m1,n1) to (m2,n2) of a sparse GF(2) matrix

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

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

Constructor, from subset of sparse GF(2) matrix.

This constructor forms a dense GF(2) matrix from a subset of columns in sparse GF(2) matrix

Parameters:

	X	matrix to copy from
	columns	subset of columns to copy

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

itpp::GF2mat::GF2mat	(	const bvec &	x,
		bool	is_column = true
	)

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

Parameters:

	x	The input vector
	is_column	A parameter that indicates whether the result should be a row vector (false), or a column vector (true - default)

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

---

Member Function Documentation

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

Add (or equivalently, subtract) rows.

This function updates row i according to row_i = row_i+row_j

Parameters:

	i	Row to add to. This row will be modified
	j	Row to add. This row will not be modified.

References it_assert.

Referenced by itpp::BLDPC_Generator::construct(), inverse(), T_fact(), T_fact_update_addcol(), and T_fact_update_bitflip().

GF2mat itpp::GF2mat::inverse

(

)

const

Inversion.

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

References add_rows(), get(), it_assert, permute_rows(), itpp::rank(), and T_fact().

Referenced by itpp::LDPC_Generator_Systematic::construct().

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

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

Parameters:

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

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

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

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

Referenced by inverse().

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

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 triangular. 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.)

The function uses Gaussian elimination combined with permutations. The computational complexity is O(m*m*n) for an m*n matrix.

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

Referenced by itpp::LDPC_Generator_Systematic::construct(), inverse(), and row_rank().

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

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 "true" if the column was added, and "false" otherwise.

Note:

This function does not actually add the column newcol to the GF2 matrix. It only checks whether doing so would increase the rank, and if this is the case, it updates the T-factorization. A typical calling sequence would be

  bool rank_will_improve =  X.T_fact_update_addcol(T,U,perm,c);
  if (rank_will_improve) { X = X.concatenate_horizontal(c); }

The complexity is O(m^2) for an m*n matrix.

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

Referenced by itpp::LDPC_Generator_Systematic::construct().

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

TXP factorization update, when bit is flipped.

Update upper triangular factor U in the TXP-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).

The function works by performing permutations to bring the matrix to a form where the Gaussian eliminated can be restarted from the point (rank-1,rank-1). The function is very fast for matrices with close to full rank but it is generally slower for non-full rank matrices.

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

---

Friends And Related Function Documentation

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

Multiplication operator with binary vector.

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

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

Multiplication operator.

GF(2) matrix multiplication.

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

Addition operator.

GF(2) matrix addition.

Subtraction is not implemented because it is equivalent to addition.

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

Write the matrix to file.

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

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

Output stream operator (plain text).

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

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

Read the matrix from file.

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

---

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

• gf2mat.h
• gf2mat.cpp