HPCombi::BMat8 Class Reference

Class for fast boolean matrices of dimension up to 8 x 8. More...

#include <bmat8.hpp>

Public Member Functions
	BMat8 () noexcept=default
	A default constructor.
	BMat8 (uint64_t mat) noexcept
	A constructor.
	BMat8 (std::vector< std::vector< bool > > const &mat)
	A constructor.
	BMat8 (BMat8 const &) noexcept=default
	A constructor.
	BMat8 (BMat8 &&) noexcept=default
	A constructor.
BMat8 &	operator= (BMat8 const &) noexcept=default
	A constructor.
BMat8 &	operator= (BMat8 &&) noexcept=default
	A constructor.
	~BMat8 ()=default
	A default destructor.
bool	operator== (BMat8 const &that) const noexcept
	Returns true if this equals that.
bool	operator!= (BMat8 const &that) const noexcept
	Returns true if this does not equal that.
bool	operator< (BMat8 const &that) const noexcept
	Returns true if this is less than that.
bool	operator> (BMat8 const &that) const noexcept
	Returns true if this is greater than that.
bool	operator() (size_t i, size_t j) const noexcept
	Returns the entry in the (i, j)th position.
void	set (size_t i, size_t j, bool val) noexcept
	Sets the (i, j)th position to val.
uint64_t	to_int () const noexcept
	Returns the integer representation of this.
BMat8	transpose () const noexcept
	Returns the transpose of this.
BMat8	transpose_mask () const noexcept
	Returns the transpose of this.
BMat8	transpose_maskd () const noexcept
	Returns the transpose of this.
BMat8	mult_transpose (BMat8 const &that) const noexcept
	Returns the matrix product of this and the transpose of that.
BMat8	operator* (BMat8 const &that) const noexcept
	Returns the matrix product of this and that.
BMat8	row_space_basis () const noexcept
	Returns a canonical basis of the row space of this.
BMat8	col_space_basis () const noexcept
	Returns a canonical basis of the col space of this.
size_t	nr_rows () const noexcept
	Returns the number of non-zero rows of this.
std::vector< uint8_t >	rows () const
	Returns a std::vector for rows of this.
uint64_t	row_space_size_ref () const
	Returns the cardinality of the row space of this.
std::bitset< 256 >	row_space_bitset_ref () const
	Returns the the row space of this.
void	row_space_bitset (epu8 &res1, epu8 &res2) const noexcept
	Returns the the row space of this as 256 bits.
uint64_t	row_space_size_bitset () const noexcept
	Returns the cardinality of the row space of this.
uint64_t	row_space_size_incl () const noexcept
	Returns the cardinality of the row space of this.
uint64_t	row_space_size_incl1 () const noexcept
	Returns the cardinality of the row space of this.
uint64_t	row_space_size () const noexcept
	Returns the cardinality of the row space of this.
bool	row_space_included_ref (BMat8 other) const noexcept
	Returns whether the row space of this is included in other's.
bool	row_space_included_bitset (BMat8 other) const noexcept
	Returns whether the row space of this is included in other's.
epu8	row_space_mask (epu8 vects) const noexcept
	Returns a mask for which vectors of a 16 rows epu8 are in the row space of this.
bool	row_space_included (BMat8 other) const noexcept
	Returns whether the row space of this is included in other's.
BMat8	row_permuted (Perm16 p) const noexcept
	Returns the matrix whose rows have been permuted according to p.
BMat8	col_permuted (Perm16 p) const noexcept
	Returns the matrix whose columns have been permuted according to p.
Perm16	right_perm_action_on_basis (BMat8) const noexcept
	Give the permutation whose right multiplication change *this to other.
Perm16	right_perm_action_on_basis_ref (BMat8) const
	Give the permutation whose right multiplication change *this to other.
void	swap (BMat8 &that) noexcept
std::ostream &	write (std::ostream &os) const
	Write this on os.

Static Public Member Functions
static void	transpose2 (BMat8 &, BMat8 &) noexcept
	Transpose two matrices at once.
static std::pair< bool, bool >	row_space_included2 (BMat8 a1, BMat8 b1, BMat8 a2, BMat8 b2)
	Returns inclusion of row spaces.
static BMat8	row_permutation_matrix (Perm16 p) noexcept
	Returns the matrix associated to the permutation p by rows.
static BMat8	col_permutation_matrix (Perm16 p) noexcept
	Returns the matrix associated to the permutation p by columns.
static BMat8	one (size_t dim=8) noexcept
	Returns the identity BMat8.
static BMat8	random ()
	Returns a random BMat8.
static BMat8	random (size_t dim)
	Returns a random square BMat8 up to dimension dim.

Detailed Description

Class for fast boolean matrices of dimension up to 8 x 8.

The methods for these small matrices over the boolean semiring are more optimised than the generic methods for boolean matrices. Note that all BMat8 are represented internally as an 8 x 8 matrix; any entries not defined by the user are taken to be 0. This does not affect the results of any calculations.

BMat8 is a trivial class.

Constructor & Destructor Documentation

BMat8() [1/5]

HPCombi::BMat8::BMat8 ( )

defaultnoexcept

A default constructor.

This constructor gives no guarantees on what the matrix will contain.

BMat8() [2/5]

HPCombi::BMat8::BMat8 ( uint64_t  mat )

inlineexplicitnoexcept

A constructor.

This constructor initializes a BMat8 to have rows equal to the 8 chunks, of 8 bits each, of the binary representation of mat.

BMat8() [3/5]

HPCombi::BMat8::BMat8 ( std::vector< std::vector< bool > > const &  mat )

inlineexplicit

A constructor.

This constructor initializes a matrix where the rows of the matrix are the vectors in mat.

BMat8() [4/5]

HPCombi::BMat8::BMat8 ( BMat8 const &  )

defaultnoexcept

A constructor.

This is the copy constructor.

BMat8() [5/5]

HPCombi::BMat8::BMat8 ( BMat8 &&  )

defaultnoexcept

A constructor.

This is the move constructor.

~BMat8()

HPCombi::BMat8::~BMat8 ( )

default

A default destructor.

Member Function Documentation

col_permutation_matrix()

BMat8 HPCombi::BMat8::col_permutation_matrix ( Perm16  p )

inlinestaticnoexcept

Returns the matrix associated to the permutation p by columns.

Parameters

p	: a permutation fixing the entries 8..15 Note: no verification is performed on p

col_permuted()

BMat8 HPCombi::BMat8::col_permuted ( Perm16  p ) const

inlinenoexcept

Returns the matrix whose columns have been permuted according to p.

Parameters

p	: a permutation fixing the entries 8..15 Note: no verification is performed on p

col_space_basis()

BMat8 HPCombi::BMat8::col_space_basis ( ) const

inlinenoexcept

Returns a canonical basis of the col space of this.

Any two matrix with the same column row space are guaranteed to have the same column space basis. Uses row_space_basis and transpose.

mult_transpose()

BMat8 HPCombi::BMat8::mult_transpose ( BMat8 const &  that ) const

inlinenoexcept

Returns the matrix product of this and the transpose of that.

This method returns the standard matrix product (over the boolean semiring) of two BMat8 objects. This is faster than transposing that and calling the product of this with it. Implementation uses vector instructions.

nr_rows()

size_t HPCombi::BMat8::nr_rows ( ) const

inlinenoexcept

Returns the number of non-zero rows of this.

one()

static BMat8 HPCombi::BMat8::one ( size_t  dim = 8 )

inlinestaticnoexcept

Returns the identity BMat8.

This method returns the 8 x 8 BMat8 with 1s on the main diagonal.

operator!=()

bool HPCombi::BMat8::operator!= ( BMat8 const &  that ) const

inlinenoexcept

Returns true if this does not equal that.

This method checks the mathematical inequality of two BMat8 objects.

operator()()

bool HPCombi::BMat8::operator() ( size_t  i, size_t  j  ) const

inlinenoexcept

Returns the entry in the (i, j)th position.

This method returns the entry in the (i, j)th position. Note that since all matrices are internally represented as 8 x 8, it is possible to access entries that you might not believe exist.

operator*()

BMat8 HPCombi::BMat8::operator* ( BMat8 const &  that ) const

inlinenoexcept

Returns the matrix product of this and that.

This method returns the standard matrix product (over the boolean semiring) of two BMat8 objects. This is a fast implementation using transposition and vector instructions.

operator<()

bool HPCombi::BMat8::operator< ( BMat8 const &  that ) const

inlinenoexcept

Returns true if this is less than that.

This method checks whether a BMat8 objects is less than another. We order by the results of to_int() for each matrix.

operator=() [1/2]

BMat8 & HPCombi::BMat8::operator= ( BMat8 &&  )

defaultnoexcept

A constructor.

This is the move assignment constructor.

operator=() [2/2]

BMat8 & HPCombi::BMat8::operator= ( BMat8 const &  )

defaultnoexcept

A constructor.

This is the copy assignment constructor.

operator==()

bool HPCombi::BMat8::operator== ( BMat8 const &  that ) const

inlinenoexcept

Returns true if this equals that.

This method checks the mathematical equality of two BMat8 objects.

operator>()

bool HPCombi::BMat8::operator> ( BMat8 const &  that ) const

inlinenoexcept

Returns true if this is greater than that.

This method checks whether a BMat8 objects is greater than another. We order by the results of to_int() for each matrix.

random() [1/2]

BMat8 HPCombi::BMat8::random ( )

inlinestatic

Returns a random BMat8.

This method returns a BMat8 chosen at random.

random() [2/2]

BMat8 HPCombi::BMat8::random ( size_t  dim )

inlinestatic

Returns a random square BMat8 up to dimension dim.

This method returns a BMat8 chosen at random, where only the top-left dim x dim entries may be non-zero.

right_perm_action_on_basis()

Perm16 HPCombi::BMat8::right_perm_action_on_basis ( BMat8  other ) const

inlinenoexcept

Give the permutation whose right multiplication change *this to other.

*this is suppose to be a row_space matrix (ie. sorted decreasingly) Fast implementation doing a vector binary search.

right_perm_action_on_basis_ref()

Perm16 HPCombi::BMat8::right_perm_action_on_basis_ref ( BMat8  bm ) const

inline

Give the permutation whose right multiplication change *this to other.

*this is suppose to be a row_space matrix (ie. sorted decreasingly) Reference implementation.

row_permutation_matrix()

BMat8 HPCombi::BMat8::row_permutation_matrix ( Perm16  p )

inlinestaticnoexcept

Returns the matrix associated to the permutation p by rows.

Parameters

p	: a permutation fixing the entries 8..15 Note: no verification is performed on p

row_permuted()

BMat8 HPCombi::BMat8::row_permuted ( Perm16  p ) const

inlinenoexcept

Returns the matrix whose rows have been permuted according to p.

Parameters

p	: a permutation fixing the entries 8..15 Note: no verification is performed on p

row_space_basis()

BMat8 HPCombi::BMat8::row_space_basis ( ) const

inlinenoexcept

Returns a canonical basis of the row space of this.

Any two matrix with the same row space are guaranteed to have the same row space basis. This is a fast implementation using vector instructions to compute in parallel the union of the other rows included in a given one.

row_space_bitset()

void HPCombi::BMat8::row_space_bitset ( epu8 &  res1, epu8 &  res2  ) const

inlinenoexcept

Returns the the row space of this as 256 bits.

The result is stored in two 128 bits registers.

row_space_bitset_ref()

std::bitset< 256 > HPCombi::BMat8::row_space_bitset_ref ( ) const

inline

Returns the the row space of this.

The result is stored in a c++ bitset

row_space_included()

bool HPCombi::BMat8::row_space_included ( BMat8  other ) const

inlinenoexcept

Returns whether the row space of this is included in other's.

Uses vector computation of the product of included rows

row_space_included2()

std::pair< bool, bool > HPCombi::BMat8::row_space_included2 ( BMat8  a1, BMat8  b1, BMat8  a2, BMat8  b2  )

inlinestatic

Returns inclusion of row spaces.

Compute at once if a1 is included in b1 and a2 is included in b2

row_space_included_bitset()

bool HPCombi::BMat8::row_space_included_bitset ( BMat8  other ) const

inlinenoexcept

Returns whether the row space of this is included in other's.

Uses a 256 bitset internally

row_space_included_ref()

bool HPCombi::BMat8::row_space_included_ref ( BMat8  other ) const

inlinenoexcept

Returns whether the row space of this is included in other's.

Uses a 256 bitset internally

row_space_mask()

epu8 HPCombi::BMat8::row_space_mask ( epu8  vects ) const

inlinenoexcept

Returns a mask for which vectors of a 16 rows epu8 are in the row space of this.

Uses vector computation of the product of included rows

row_space_size()

uint64_t HPCombi::BMat8::row_space_size ( ) const

inlinenoexcept

Returns the cardinality of the row space of this.

Alias to row_space_size_incl

row_space_size_bitset()

uint64_t HPCombi::BMat8::row_space_size_bitset ( ) const

inlinenoexcept

Returns the cardinality of the row space of this.

It compute all the product using two 128 bits registers to store the set of elements of the row space.

row_space_size_incl()

uint64_t HPCombi::BMat8::row_space_size_incl ( ) const

inlinenoexcept

Returns the cardinality of the row space of this.

Uses vector computation of the product of included rows in each 256 possible vectors. Fastest implementation saving a few instructions compared to row_space_size_incl1

row_space_size_incl1()

uint64_t HPCombi::BMat8::row_space_size_incl1 ( ) const

inlinenoexcept

Returns the cardinality of the row space of this.

Uses vector computation of the product included row in each 256 possible vectors. More optimized in row_space_size_incl

row_space_size_ref()

uint64_t HPCombi::BMat8::row_space_size_ref ( ) const

inline

Returns the cardinality of the row space of this.

Reference implementation computing all products

rows()

std::vector< uint8_t > HPCombi::BMat8::rows ( ) const

inline

Returns a std::vector for rows of this.

set()

void HPCombi::BMat8::set ( size_t  i, size_t  j, bool  val  )

inlinenoexcept

Sets the (i, j)th position to val.

This method sets the (i, j)th entry of this to val. Uses the bit twiddle for setting bits found here.

swap()

void HPCombi::BMat8::swap ( BMat8 &  that )

inlinenoexcept

to_int()

uint64_t HPCombi::BMat8::to_int ( ) const

inlinenoexcept

Returns the integer representation of this.

Returns an unsigned integer obtained by interpreting an 8 x 8 BMat8 as a sequence of 64 bits (reading rows left to right, from top to bottom) and then this sequence as an unsigned int.

transpose()

BMat8 HPCombi::BMat8::transpose ( ) const

inlinenoexcept

Returns the transpose of this.

Returns the standard matrix transpose of a BMat8. Uses the technique found in Knuth AoCP Vol. 4 Fasc. 1a, p. 15.

transpose2()

void HPCombi::BMat8::transpose2 ( BMat8 &  a, BMat8 &  b  )

inlinestaticnoexcept

Transpose two matrices at once.

Compute in parallel the standard matrix transpose of two BMat8. Uses the technique found in Knuth AoCP Vol. 4 Fasc. 1a, p. 15.

transpose_mask()

BMat8 HPCombi::BMat8::transpose_mask ( ) const

inlinenoexcept

Returns the transpose of this.

Returns the standard matrix transpose of a BMat8. Uses movemask instruction.

transpose_maskd()

BMat8 HPCombi::BMat8::transpose_maskd ( ) const

inlinenoexcept

Returns the transpose of this.

Returns the standard matrix transpose of a BMat8. Uses movemask instruction.

write()

std::ostream & HPCombi::BMat8::write ( std::ostream &  os ) const

inline

Write this on os.

---

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

• /Users/jdm/hpcombi/include/hpcombi/bmat8.hpp
• /Users/jdm/hpcombi/include/hpcombi/bmat8_impl.hpp