gf2::BitGauss< Word >

The BitGauss class is a Gaussian elimination solver for systems of linear equations over GF(2).
It solves systems of the form \(A \cdot x = b\) where A is a square matrix, x is a vector of unknowns, and b is the known right-hand side vector. More...

#include <BitGauss.h>

Public Member Functions
template<typename Store> requires store_word_is<Store, Word>
	BitGauss (const BitMat< Word > &A, const BitStore< Store > &b)
	Constructs a new BitGauss object where we are solving the system of linear equations A.x = b.
constexpr usize	rank () const
	Returns the rank of the matrix A.
constexpr usize	free_count () const
	Returns the number of free variables in the system.
constexpr bool	is_underdetermined () const
	Returns true if the system is underdetermined.
constexpr bool	is_consistent () const
	Returns true if the system of linear equations A.x_for = b is consistent.
constexpr usize	solution_count () const
	Returns the maximum number of solutions we can index into.
std::optional< BitVec< Word > >	operator() () const
	Returns a solution to the system of linear equations A.x_for = b or std::nullopt if the system is inconsistent.
std::optional< BitVec< Word > >	operator() (usize i_solution) const
	Returns the ith solution to the system of linear equations A.x_for = b or std::nullopt if the system is inconsistent or if i is out of bounds.

Detailed Description

template<unsigned_word Word>
class gf2::BitGauss< Word >

The BitGauss class is a Gaussian elimination solver for systems of linear equations over GF(2).
It solves systems of the form \(A \cdot x = b\) where A is a square matrix, x is a vector of unknowns, and b is the known right-hand side vector.

Over the reals, systems of linear equations can have 0, 1, or, if the system is underdetermined, an infinite number of solutions. By contrast, over GF(2), in an underdetermined system, the number of solutions is 2^f where f is the number of "free" variables". This is because underdetermined variables can be set to one of just two values. Therefore, over GF(2) the number of solutions is 0, 1, or 2^f where <tt>f</tt> is the number of free variables. If the system is consistent then we can index into the solutions by an integer <tt>i</tt> where <tt>0 \<= i \< 2^f</tt>. - The <tt>BitGauss::operator()</tt> method returns a random solution. - The <tt>BitGauss::operator(i)</tt> method returns "the" solution indexed <tt>i</tt>. For underdetermined systems, the "indexing" is something convenient and consistent across runs but not unique.

Note

The BitLU class provides another, often more efficient, way to solve systems of linear equations over GF(2). It also provides the BitLU::inverse method for computing the inverse of a matrix.

Example

auto A = BitMat<>::ones(3, 3);
auto b = BitVec<>::ones(3);
auto solver = A.solver_for(b);
assert_eq(solver.rank(), 1);
assert_eq(solver.free_count(), 2);
assert_eq(solver.solution_count(), 4);
assert_eq(solver.is_underdetermined(), true);
assert_eq(solver.is_consistent(), true);

Constructor & Destructor Documentation

BitGauss()

template<unsigned_word Word>

template<typename Store>
requires store_word_is<Store, Word>

gf2::BitGauss< Word >::BitGauss ( const BitMat< Word > & A, const BitStore< Store > & b )

inline

Constructs a new BitGauss object where we are solving the system of linear equations A.x = b.

Note

Panics if the A matrix is not square or if the A matrix and b vector have a different number of rows

Example

auto A = BitMat<>::ones(3, 3);
auto b = BitVec<>::ones(3);
BitGauss solver{A, b};
assert_eq(solver.rank(), 1);
assert_eq(solver.is_underdetermined(), true);
assert_eq(solver.is_consistent(), true);
assert_eq(solver.free_count(), 2);
assert_eq(solver.solution_count(), 4);

Member Function Documentation

free_count()

template<unsigned_word Word>

usize gf2::BitGauss< Word >::free_count ( ) const

inlineconstexpr

Returns the number of free variables in the system.

Example

auto A = BitMat<>::ones(3, 3);
auto b = BitVec<>::ones(3);
auto solver = A.solver_for(b);
assert_eq(solver.free_count(), 2);

is_consistent()

template<unsigned_word Word>

bool gf2::BitGauss< Word >::is_consistent ( ) const

inlineconstexpr

Returns true if the system of linear equations A.x_for = b is consistent.

A system is consistent if there is at least one solution.

Example

auto A = BitMat<>::ones(3, 3);
auto b = BitVec<>::ones(3);
auto solver = A.solver_for(b);
assert_eq(solver.is_consistent(), true);

is_underdetermined()

template<unsigned_word Word>

bool gf2::BitGauss< Word >::is_underdetermined ( ) const

inlineconstexpr

Returns true if the system is underdetermined.

Example

auto A = BitMat<>::ones(3, 3);
auto b = BitVec<>::ones(3);
auto solver = A.solver_for(b);
assert_eq(solver.is_underdetermined(), true);

operator()() [1/2]

template<unsigned_word Word>

std::optional< BitVec< Word > > gf2::BitGauss< Word >::operator() ( ) const

inline

Returns a solution to the system of linear equations A.x_for = b or std::nullopt if the system is inconsistent.

If the system is underdetermined with f free variables the returned solution will have f random 0/1 entries for those indices.

Example

auto A = BitMat<>::identity(3);
auto b = BitVec<>::ones(3);
auto solver = A.solver_for(b);
assert_eq(solver().value().to_string(), "111");

operator()() [2/2]

template<unsigned_word Word>

std::optional< BitVec< Word > > gf2::BitGauss< Word >::operator() ( usize i_solution ) const

inline

Returns the ith solution to the system of linear equations A.x_for = b or std::nullopt if the system is inconsistent or if i is out of bounds.

If the system is consistent and determined, there is a unique solution and operator()(0) is the same as operator()().

If the system is underdetermined with f free variables, it has 2^f possible solutions. If f is large, 2^f may not fit in usize but here we limit the number of indexable solutions to the largest power of 2 that fits in usize. The indexing scheme is certainly not unique but it is consistent across runs.

Example

auto A = BitMat<>::ones(3, 3);
auto b = BitVec<>::ones(3);
auto solver = A.solver_for(b);
assert_eq(solver.solution_count(), 4);
assert_eq(solver(0).value().to_string(), "100");
assert_eq(solver(1).value().to_string(), "010");
assert_eq(solver(2).value().to_string(), "001");
assert_eq(solver(3).value().to_string(), "111");

rank()

template<unsigned_word Word>

usize gf2::BitGauss< Word >::rank ( ) const

inlineconstexpr

Returns the rank of the matrix A.

Example

auto A = BitMat<>::ones(3, 3);
auto b = BitVec<>::ones(3);
auto solver = A.solver_for(b);
assert_eq(solver.rank(), 1);

solution_count()

template<unsigned_word Word>

usize gf2::BitGauss< Word >::solution_count ( ) const

inlineconstexpr

Returns the maximum number of solutions we can index into.

This may be 0, 1, or 2^f for some f where f is the number of free variables in an underdetermined system. For the xi_for(i: usize) function we limit that to the largest power of 2 that fits in usize.

If usize is 64 bits then solution_count = min(2^f, 2^63).

Example

auto A = BitMat<>::ones(3, 3);
auto b = BitVec<>::ones(3);
auto solver = A.solver_for(b);
assert_eq(solver.solution_count(), 4);