`GF2::Matrix` — Bit-Matrix Multiplication

Computes the dot product of a bit-vector with a bit-matrix, a bit-matrix with a bit-vector, and a bit-matrix with another.

template<std::unsigned_integral Block, typename Allocator>
constexpr const Vector<Block, Allocator>
dot(const Matrix<Block, Allocator> &M, const Vector<Block, Allocator> &v);  (1)

template<std::unsigned_integral Block, typename Allocator>
constexpr const Vector<Block, Allocator>
dot(const Vector<Block, Allocator> &v, const Matrix<Block, Allocator> &M);  (2)

template<std::unsigned_integral Block, typename Allocator>
constexpr const Matrix<Block, Allocator>
dot(const Matrix<Block, Allocator> &M, const Matrix<Block, Allocator> &N);  (3)

1	Computes \(M \cdot v\). If `M` is `r x c` then `v.size()` must be `c`. The returned bit-vector will have size `r`.
2	Computes \(v \cdot M\). If `M` is `r x c` then `v.size()` must be `r`. The returned bit-vector will have size `c`.
3	Computes \(M \cdot N\). If `M` is `a x b` then `N` must be `b x c` for some `c`. The returned bit-matrix will be `a x c`.

These dot products are defined by:

\[\begin{aligned} \left(M \cdot v\right)_i &= \sum_j M_{ij} \times v_j \\ \left(v \cdot M\right)_j &= \sum_i v_i \times M_{ij} \\ \left(M \cdot N\right)_{ij} &= \sum_k M_{ik} \times N_{kj} \end{aligned}\]

In the case of GF(2), product is replaced by logical AND, and sum by the logical XOR operation.

The dot product is a key operation in linear algebra so it fortunate that AND’ing and XOR’ing for bit-matrices and bit-vectors can be done very efficiently over blocks of elements at a time.

The two arguments in each case must have compatible sizes. If the GF2_DEBUG flag is set at compile time this is checked and any violation will cause the program to abort with a helpful message.

Example

#include <GF2/GF2.h>
int main()
{
    GF2::Vector<> u(6, [](size_t k) { return k % 2; });
    GF2::Vector<> v(8, [](size_t k) { return (k + 1)% 2; });

    GF2::Matrix<> M(6, 8, [](size_t i, size_t j) { return i == j; });
    GF2::Matrix<> N(8, 4, [](size_t i, size_t j) { return (i + j)%2; });

    std::cout << "Matrix M:\n" << M << '\n';
    std::cout << "Matrix N:\n" << N << '\n';

    std::cout << "dot(" << u << ", M): " << dot(u, M) << '\n';
    std::cout << "dot(M, " << v << "): " << dot(M, v) << '\n';
    std::cout << "dot(M, N):\n" << dot(M, N) << '\n';
}

Output

Matrix M:
10000000
01000000
00100000
00010000
00001000
00000100
Matrix N:
0101
1010
0101
1010
0101
1010
0101
1010
dot(010101, M): 01010100
dot(M, 10101010): 101010
dot(M, N):
0101
1010
0101
1010
0101
1010

GF2::Matrix — Bit-Matrix Multiplication

`GF2::Matrix` — Bit-Matrix Multiplication