GF2::GaussSolver
Overview
A GF2::GaussSolver object is used to find solutions for the system of linear equations \(A \cdot x = b\) over \(\mathbb{F}_2\).
Here \(A\) is a known bit-matrix, \(b\) a known right hand side bit-vector, while \(x\) is the unknown solution to the system. \(A\) should be square and the size of the \(b\) should match the number of rows in \(A\).
As the name suggests, the solution method used is Gaussian elimination or more specifically Gauss-Jordan elimination.
On construction, the GF2::GaussSolver object captures copies of \(A\) and \(b\) and then uses elementary row operations to transform the left hand side matrix to reduced row echelon form while simultaneously performing the identical operations to the right hand side vector.
With those in place the solver can quickly produce solutions \(x\) by simple back-substitution.
As well as getting solutions for the system \(A \cdot x = b\) the GF2::GaussSolver object can be queried for other useful information such as the rank of \(A\), whether the system is consistent (i.e. whether any solutions at all exist), and so on.
See the full list below.
Recognizing that often one just wants to find a solution to \(A \cdot x = b\) with a minimum of palaver there is a non-member function to do just that which can be invoked as follows:
...
auto x = GF2::solve(A,b);
if(x) {
...
}The x here is a bit-vector wrapped in a std::optional.
If no solution exists x will be a std::nullopt otherwise it can safely be dereferenced as a GF2::Vector.
A system of linear equations over \(\mathbb{R}\) has either no solutions, one solution, or an infinite number of solutions. The latter situation arises if the system in under-determined so that there is one or more free variables.
Generally speaking if you have \(m\) independent and consistent equations for \(n\) unknowns and \(n>m\) then there are \(f=n-m\) free variables. Reducing the matrix to echelon form lets you find out just how many independent equations you really have and also lets you quickly check that the system is consistent. Over \(\mathbb{R}\) a free variable can take on any value hence there are an infinite number of possible solutions to the system.
Over \(\mathbb{F}_2\) the situation is different because a free variable can only take on one of the two values 0 and 1. Hence if the system is consistent and has \(f\) free variables it will have \(2^f\) possible solutions. So if there are no free variables then a consistent system will have one unique solution.
That x in the example above will be one of those \(2^f\) possible solutions picked completely at random.
We also provide a way to iterate through a lot of the possible solutions (not necessarily all of them because if \(f\) is large the number of possible solutions explodes).
If solver is a GF2::GaussSolver for the consistent system \(A \cdot x = b\) with \(f\) free variables then the call solver() will return one of the possible \(2^f\) solutions picked completely at random (calling solver() again may well return a different but equally valid solution).
On the other hand, a call to solver(n), where n is a std::size_t and \(n < 2^f), will produce a specific solution.
There are lots of ways to produce an ordering amongst the possible solutions but in any case that call to solver(n) will always produce the same solution.
Declaration
The GF2::GaussSolver class is defined in the header <GF2/GaussSolver.h> as follows:
namespace GF2 {
template<
std::unsigned_integral Block = uint64_t,
Allocator = std::allocator<Block>
> class GaussSolver;
}See the documentation for GF2::Vector and GF2::Matrix for more information on the two template parameters.
Class Types
Type |
Definition |
|---|---|
|
An alias for |
|
An alias for |
Methods
Construction |
|
|---|---|
Create a |
|
Queries |
|
Various queries about the state of the system. |
|
Echelon Form Access |
|
Read access to the reduced row echelon form for \(A\) and the equivalently manipulated version of \(b\) |
|
Access a specific or a random solution for the system \(A \cdot x = b\). |
|