HPCombi
High Performance Combinatorics in C++ using vector instructions v1.1.0
|
Boolean matrices of dimension up to 8×8, stored as a single uint64; isomorph to binary relations with methods for composition. More...
#include <bmat8.hpp>
Public Member Functions | |
BMat8 () noexcept=default | |
BMat8 (uint64_t mat) noexcept | |
BMat8 (std::vector< std::vector< bool > > const &mat) | |
BMat8 (BMat8 const &) noexcept=default | |
BMat8 (BMat8 &&) noexcept=default | |
BMat8 & | operator= (BMat8 const &) noexcept=default |
BMat8 & | operator= (BMat8 &&) noexcept=default |
~BMat8 ()=default | |
A default destructor. | |
bool | operator== (BMat8 const &that) const noexcept |
bool | operator!= (BMat8 const &that) const noexcept |
bool | operator< (BMat8 const &that) const noexcept |
bool | operator> (BMat8 const &that) const noexcept |
bool | operator() (size_t i, size_t j) const noexcept |
void | set (size_t i, size_t j, bool val) noexcept |
uint64_t | to_int () const noexcept |
std::array< std::array< bool, 8 >, 8 > | to_array () const noexcept |
BMat8 | operator| (BMat8 const &that) const noexcept |
BMat8 | transpose_naive () const noexcept |
BMat8 | transpose () const noexcept |
BMat8 | transpose_mask () const noexcept |
BMat8 | transpose_maskd () const noexcept |
BMat8 | mult_transpose (BMat8 const &that) const noexcept |
BMat8 | operator* (BMat8 const &that) const noexcept |
BMat8 | mult_naive (BMat8 const &that) const noexcept |
BMat8 | mult_naive_array (BMat8 const &that) const noexcept |
BMat8 | row_space_basis () const noexcept |
BMat8 | col_space_basis () const noexcept |
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 |
std::bitset< 256 > | row_space_bitset_ref () const |
void | row_space_bitset (epu8 &res1, epu8 &res2) const noexcept |
uint64_t | row_space_size_bitset () const noexcept |
uint64_t | row_space_size_incl () const noexcept |
uint64_t | row_space_size_incl1 () const noexcept |
uint64_t | row_space_size () const noexcept |
bool | row_space_included_ref (BMat8 other) const noexcept |
bool | row_space_included_bitset (BMat8 other) const noexcept |
epu8 | row_space_mask (epu8 vects) const noexcept |
bool | row_space_included (BMat8 other) const noexcept |
BMat8 | row_permuted (Perm16 p) const noexcept |
BMat8 | col_permuted (Perm16 p) const noexcept |
Perm16 | right_perm_action_on_basis (BMat8) const noexcept |
Perm16 | right_perm_action_on_basis_ref (BMat8) const |
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 |
static std::pair< bool, bool > | row_space_included2 (BMat8 a1, BMat8 b1, BMat8 a2, BMat8 b2) |
static BMat8 | row_permutation_matrix (Perm16 p) noexcept |
static BMat8 | col_permutation_matrix (Perm16 p) noexcept |
static BMat8 | one (size_t dim=8) noexcept |
static BMat8 | random () |
static BMat8 | random (size_t dim) |
Boolean matrices of dimension up to 8×8, stored as a single uint64; isomorph to binary relations with methods for composition.
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×8 matrix; any entries not defined by the user are taken to be 0. This does not affect the results of any calculation.
BMat8 is a trivial class.
|
defaultnoexcept |
A default constructor.
This constructor gives no guarantees on what the matrix will contain.
|
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
.
|
inlineexplicit |
A constructor.
This constructor initializes a matrix where the rows of the matrix are the vectors in mat
.
|
defaultnoexcept |
A constructor.
This is the copy constructor.
|
defaultnoexcept |
A constructor.
This is the move constructor.
|
default |
A default destructor.
Returns the matrix associated to the permutation p
by columns
p | : a permutation fixing the entries 8..15 Note: no verification is performed on p |
Returns the matrix whose columns have been permuted according to p
p | : a permutation fixing the entries 8..15 Note: no verification is performed on p |
|
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.
Returns the matrix product of this
and that
This method returns the standard matrix product (over the boolean semiring) of two BMat8 objects. It performs the most naive approach by simply iterating through all entries using array conversion.
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.
|
inlinenoexcept |
Returns the number of non-zero rows of this
.
|
inlinestaticnoexcept |
|
inlinenoexcept |
Returns true
if this
does not equal that
This method checks the mathematical inequality of two BMat8 objects.
|
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.
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.
|
inlinenoexcept |
A constructor.
This is the move assignment constructor.
A constructor.
This is the copy assignment constructor.
|
inlinenoexcept |
Returns true
if this
equals that
.
This method checks the mathematical equality of two BMat8 objects.
|
inlinenoexcept |
Returns the bitwise or between this
and that
This method perform the bitwise operator on the matrices and returns the result as a BMat8
|
inlinestatic |
|
inlinestatic |
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.
Give the permutation whose right multiplication change *this
to other
*this
is suppose to be a row_space matrix (ie. sorted decreasingly) Reference implementation.
Returns the matrix associated to the permutation p
by rows
p | : a permutation fixing the entries 8..15 Note: no verification is performed on p |
Returns the matrix whose rows have been permuted according to p
p | : a permutation fixing the entries 8..15 Note: no verification is performed on p |
|
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.
Returns the the row space of this
as 256 bits.
The result is stored in two 128 bits registers.
|
inline |
Returns the the row space of this
The result is stored in a c++ bitset
|
inlinenoexcept |
Returns whether the row space of this
is included in other's
Uses vector computation of the product of included rows
|
inlinestatic |
Returns inclusion of row spaces
Compute at once if a1 is included in b1 and a2 is included in b2
|
inlinenoexcept |
Returns whether the row space of this
is included in other's
Uses a 256 bitset internally
|
inlinenoexcept |
Returns whether the row space of this
is included in other's
Uses a 256 bitset internally
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
|
inlinenoexcept |
Returns the cardinality of the row space of this
Alias to row_space_size_incl
|
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.
|
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
|
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
|
inline |
Returns the cardinality of the row space of this
Reference implementation computing all products
|
inline |
Returns a std::vector
for rows of this
.
|
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.
|
inlinenoexcept |
|
inlinenoexcept |
Returns the array representation of this
.
Returns a two dimensional 8 x 8 array representing the matrix.
|
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.
|
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.
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.
|
inlinenoexcept |
Returns the transpose of this
Returns the standard matrix transpose of a BMat8. Uses movemask
instruction.
|
inlinenoexcept |
Returns the transpose of this
Returns the standard matrix transpose of a BMat8. Uses movemask
instruction.
|
inlinenoexcept |
Returns the transpose of this
.
Returns the standard matrix transpose of a BMat8. Uses a naive technique, by simply iterating through all entries
|
inline |
Write this
on os
.