HPCombi
High Performance Combinatorics in C++ using vector instructions v1.0.2
Loading...
Searching...
No Matches
bmat8.hpp
Go to the documentation of this file.
1//****************************************************************************//
2// Copyright (C) 2018-2024 Finn Smith <fls3@st-andrews.ac.uk> //
3// Copyright (C) 2018-2024 James Mitchell <jdm3@st-andrews.ac.uk> //
4// Copyright (C) 2018-2024 Florent Hivert <Florent.Hivert@lisn.fr>, //
5// //
6// This file is part of HP-Combi <https://github.com/libsemigroups/HPCombi> //
7// //
8// HP-Combi is free software: you can redistribute it and/or modify it //
9// under the terms of the GNU General Public License as published by the //
10// Free Software Foundation, either version 3 of the License, or //
11// (at your option) any later version. //
12// //
13// HP-Combi is distributed in the hope that it will be useful, but WITHOUT //
14// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or //
15// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License //
16// for more details. //
17// //
18// You should have received a copy of the GNU General Public License along //
19// with HP-Combi. If not, see <https://www.gnu.org/licenses/>. //
20//****************************************************************************//
21
24
25#ifndef HPCOMBI_BMAT8_HPP_
26#define HPCOMBI_BMAT8_HPP_
27
28#include <array> // for array
29#include <bitset> // for bitset
30#include <cstddef> // for size_t
31#include <cstdint> // for uint64_t, uint8_t
32#include <functional> // for hash, __scalar_hash
33#include <iostream> // for ostream
34#include <memory> // for hash
35#include <utility> // for pair, swap
36#include <vector> // for vector
37
38#include "debug.hpp" // for HPCOMBI_ASSERT
39#include "epu8.hpp" // for epu8
40#include "perm16.hpp" // for Perm16
41
42namespace HPCombi {
43
55class BMat8 {
56 public:
60 BMat8() noexcept = default;
61
66 explicit BMat8(uint64_t mat) noexcept : _data(mat) {}
67
72 // Not sure if this is noexcept or not
73 explicit BMat8(std::vector<std::vector<bool>> const &mat);
74
78 BMat8(BMat8 const &) noexcept = default;
79
83 BMat8(BMat8 &&) noexcept = default;
84
88 BMat8 &operator=(BMat8 const &) noexcept = default;
89
93 BMat8 &operator=(BMat8 &&) noexcept = default;
94
96 ~BMat8() = default;
97
101 bool operator==(BMat8 const &that) const noexcept {
102 return _data == that._data;
103 }
104
108 bool operator!=(BMat8 const &that) const noexcept {
109 return _data != that._data;
110 }
111
116 bool operator<(BMat8 const &that) const noexcept {
117 return _data < that._data;
118 }
119
124 bool operator>(BMat8 const &that) const noexcept {
125 return _data > that._data;
126 }
127
133 bool operator()(size_t i, size_t j) const noexcept;
134
140 void set(size_t i, size_t j, bool val) noexcept;
141
147 uint64_t to_int() const noexcept { return _data; }
148
153 BMat8 transpose() const noexcept;
154
159 BMat8 transpose_mask() const noexcept;
160
165 BMat8 transpose_maskd() const noexcept;
166
171 static void transpose2(BMat8 &, BMat8 &) noexcept;
172
179 BMat8 mult_transpose(BMat8 const &that) const noexcept;
180
186 BMat8 operator*(BMat8 const &that) const noexcept {
187 return mult_transpose(that.transpose());
188 }
189
196 BMat8 row_space_basis() const noexcept;
197
202 BMat8 col_space_basis() const noexcept {
204 }
205
207 size_t nr_rows() const noexcept;
208
210 // Not noexcept because it constructs a vector
211 std::vector<uint8_t> rows() const;
212
216 // Not noexcept because row_space_bitset_ref isn't
217 uint64_t row_space_size_ref() const;
218
222 // Not noexcept because it creates a vector
223 std::bitset<256> row_space_bitset_ref() const;
224
228 void row_space_bitset(epu8 &res1, epu8 &res2) const noexcept;
229
234 uint64_t row_space_size_bitset() const noexcept;
235
241 uint64_t row_space_size_incl() const noexcept;
242
247 uint64_t row_space_size_incl1() const noexcept;
248
252 uint64_t row_space_size() const noexcept { return row_space_size_incl(); }
253
257 bool row_space_included_ref(BMat8 other) const noexcept;
258
262 bool row_space_included_bitset(BMat8 other) const noexcept;
263
268 epu8 row_space_mask(epu8 vects) const noexcept;
269
273 bool row_space_included(BMat8 other) const noexcept;
274
278 // Not noexcept because std::make_pair is not
279 static std::pair<bool, bool> row_space_included2(BMat8 a1, BMat8 b1,
280 BMat8 a2, BMat8 b2);
281
286 BMat8 row_permuted(Perm16 p) const noexcept;
287
292 BMat8 col_permuted(Perm16 p) const noexcept;
293
298 static BMat8 row_permutation_matrix(Perm16 p) noexcept;
299
304 static BMat8 col_permutation_matrix(Perm16 p) noexcept;
305
312
318 // Not noexcept because vectors are allocated
320
324 static BMat8 one(size_t dim = 8) noexcept {
325 HPCOMBI_ASSERT(dim <= 8);
326 static std::array<uint64_t, 9> const ones = {
327 0x0000000000000000, 0x8000000000000000, 0x8040000000000000,
328 0x8040200000000000, 0x8040201000000000, 0x8040201008000000,
329 0x8040201008040000, 0x8040201008040200, 0x8040201008040201};
330 return BMat8(ones[dim]);
331 }
332
336 // Not noexcept because random things aren't
337 static BMat8 random();
338
343 // Not noexcept because BMat8::random above is not
344 static BMat8 random(size_t dim);
345
346 void swap(BMat8 &that) noexcept { std::swap(this->_data, that._data); }
347
349 // Not noexcept
350 std::ostream &write(std::ostream &os) const;
351
352#ifdef HPCOMBI_HAVE_DENSEHASHMAP
353 // FIXME do this another way
354 BMat8 empty_key() const noexcept { return BMat8(0xFF7FBFDFEFF7FBFE); }
355#endif
356
357 private:
358 uint64_t _data;
359
360 epu8 row_space_basis_internal() const noexcept;
361};
362
363} // namespace HPCombi
364
365#include "bmat8_impl.hpp"
366
367namespace std {
368template <> struct hash<HPCombi::BMat8> {
369 inline size_t operator()(HPCombi::BMat8 const &bm) const {
370 return hash<uint64_t>()(bm.to_int());
371 }
372};
373} // namespace std
374#endif // HPCOMBI_BMAT8_HPP_
uint8_t __attribute__((vector_size(16))) epu8
epu8 stands for Extended Packed Unsigned, grouped by 8 bits; this is the low level type chosen by Int...
Definition epu8.hpp:66
Boolean matrices of dimension up to 8×8, stored as a single uint64; isomorph to binary relations with...
Definition bmat8.hpp:55
uint64_t row_space_size_incl() const noexcept
Returns the cardinality of the row space of this.
Definition bmat8_impl.hpp:317
BMat8 row_space_basis() const noexcept
Returns a canonical basis of the row space of this.
Definition bmat8_impl.hpp:239
static std::pair< bool, bool > row_space_included2(BMat8 a1, BMat8 b1, BMat8 a2, BMat8 b2)
Returns inclusion of row spaces.
Definition bmat8_impl.hpp:362
static void transpose2(BMat8 &, BMat8 &) noexcept
Transpose two matrices at once.
Definition bmat8_impl.hpp:190
uint64_t row_space_size_bitset() const noexcept
Returns the cardinality of the row space of this.
Definition bmat8_impl.hpp:292
static BMat8 row_permutation_matrix(Perm16 p) noexcept
Returns the matrix associated to the permutation p by rows.
Definition bmat8_impl.hpp:437
BMat8 mult_transpose(BMat8 const &that) const noexcept
Returns the matrix product of this and the transpose of that.
Definition bmat8_impl.hpp:210
BMat8(BMat8 const &) noexcept=default
A constructor.
BMat8 transpose_maskd() const noexcept
Returns the transpose of this.
Definition bmat8_impl.hpp:176
BMat8(BMat8 &&) noexcept=default
A constructor.
bool row_space_included_bitset(BMat8 other) const noexcept
Returns whether the row space of this is included in other's.
Definition bmat8_impl.hpp:333
bool operator>(BMat8 const &that) const noexcept
Returns true if this is greater than that.
Definition bmat8.hpp:124
BMat8 transpose() const noexcept
Returns the transpose of this.
Definition bmat8_impl.hpp:153
static BMat8 col_permutation_matrix(Perm16 p) noexcept
Returns the matrix associated to the permutation p by columns.
Definition bmat8_impl.hpp:441
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.
Definition bmat8_impl.hpp:352
BMat8 row_permuted(Perm16 p) const noexcept
Returns the matrix whose rows have been permuted according to p.
Definition bmat8_impl.hpp:425
BMat8() noexcept=default
A default constructor.
BMat8 col_space_basis() const noexcept
Returns a canonical basis of the col space of this.
Definition bmat8.hpp:202
bool row_space_included(BMat8 other) const noexcept
Returns whether the row space of this is included in other's.
Definition bmat8_impl.hpp:341
std::ostream & write(std::ostream &os) const
Write this on os.
Definition bmat8_impl.hpp:486
void row_space_bitset(epu8 &res1, epu8 &res2) const noexcept
Returns the the row space of this as 256 bits.
Definition bmat8_impl.hpp:277
Perm16 right_perm_action_on_basis(BMat8) const noexcept
Give the permutation whose right multiplication change *this to other.
Definition bmat8_impl.hpp:476
std::bitset< 256 > row_space_bitset_ref() const
Returns the the row space of this.
Definition bmat8_impl.hpp:376
bool operator!=(BMat8 const &that) const noexcept
Returns true if this does not equal that.
Definition bmat8.hpp:108
BMat8 col_permuted(Perm16 p) const noexcept
Returns the matrix whose columns have been permuted according to p.
Definition bmat8_impl.hpp:433
uint64_t to_int() const noexcept
Returns the integer representation of this.
Definition bmat8.hpp:147
uint64_t row_space_size_ref() const
Returns the cardinality of the row space of this.
Definition bmat8_impl.hpp:404
uint64_t row_space_size() const noexcept
Returns the cardinality of the row space of this.
Definition bmat8.hpp:252
BMat8 transpose_mask() const noexcept
Returns the transpose of this.
Definition bmat8_impl.hpp:164
void swap(BMat8 &that) noexcept
Definition bmat8.hpp:346
static BMat8 one(size_t dim=8) noexcept
Returns the identity BMat8.
Definition bmat8.hpp:324
std::vector< uint8_t > rows() const
Returns a std::vector for rows of this.
Definition bmat8_impl.hpp:408
size_t nr_rows() const noexcept
Returns the number of non-zero rows of this.
Definition bmat8_impl.hpp:417
void set(size_t i, size_t j, bool val) noexcept
Sets the (i, j)th position to val.
Definition bmat8_impl.hpp:111
static BMat8 random()
Returns a random BMat8.
Definition bmat8_impl.hpp:135
bool operator()(size_t i, size_t j) const noexcept
Returns the entry in the (i, j)th position.
Definition bmat8_impl.hpp:105
bool operator<(BMat8 const &that) const noexcept
Returns true if this is less than that.
Definition bmat8.hpp:116
uint64_t row_space_size_incl1() const noexcept
Returns the cardinality of the row space of this.
Definition bmat8_impl.hpp:301
bool row_space_included_ref(BMat8 other) const noexcept
Returns whether the row space of this is included in other's.
Definition bmat8_impl.hpp:398
Perm16 right_perm_action_on_basis_ref(BMat8) const
Give the permutation whose right multiplication change *this to other.
Definition bmat8_impl.hpp:445
defines the macro HPCOMBI_ASSERT
#define HPCOMBI_ASSERT(x)
Definition debug.hpp:31
declaration of HPCombi::epu8.
const Transf16 a1
Definition image.cpp:52
const Transf16 a2
Definition image.cpp:53
Definition bmat8.hpp:42
uint8_t __attribute__((vector_size(16))) epu8
epu8 stands for Extended Packed Unsigned, grouped by 8 bits; this is the low level type chosen by Int...
Definition epu8.hpp:66
Definition bmat8.hpp:367
declaration of PTransf16, Transf16, PPerm16 and Perm16
Permutations of : A permutation is a bijective mapping of a set of n elements onto itself.
Definition perm16.hpp:230
size_t operator()(HPCombi::BMat8 const &bm) const
Definition bmat8.hpp:369