GF2::GaussSolver — Construction

Construction of a GaussSolver.

Class constructor

GaussSolver(const GF2::Matrix &A, const GF2::Vector &b);

Factory function

GaussSolver gauss_solver(const GF2::Matrix &A, const GF2::Vector &b);

These construct a GaussSolver object for the system \(A \cdot x = b\) where \(A\) is a square bit-matrix and \(b\) is bit-vector of the same size as there are rows in \(A\).

On construction a GaussSolver computes the reduced row echelon form of \(A\) by using elementary row operations. It performs the same operations to a copy of the input bit-vector \(b\). Once that is done it can readily compute the rank of \(A\), check the system for consistency, compute the number of free variables etc.

If \(A\) is \(n \times n\) then construction is an \(\mathcal{O}(n^3)\) operation (though due to the nature of \(\mathbb{F}_2\) things are done in blocks at a time). There are potentially sub-cubic ways of doing this work using various block-iterative methods that are not implemented here yet.

Example

#include <GF2/GF2.h>
int
main()
{
    std::size_t m = 12;

    auto A = GF2::Matrix<>::random(m);
    auto b = GF2::Vector<>::random(m);
    std::cout << "Solving the system A.x = b for the following A & b:\n";
    print(A, b);

    // Create a solver object for the system
    auto solver = GF2::gauss_solver(A, b);

    // Print some general information
    std::cout << "Number of equations in system:   " << solver.equation_count() << '\n';
    std::cout << "Rank of the matrix A:            " << solver.rank()           << '\n';
    std::cout << "Number of free variables:        " << solver.free_count()     << '\n';
    std::cout << "Number of solutions to A.x = b:  " << solver.solution_count() << '\n';

    // Also have a look at the echelon form of A and the equivalently transformed b
    std::cout << "The echelon forms of A & b are:\n";
    print(solver.lhs(), solver.rhs());
}

Output (depends on the values of the random inputs)

Solving the system A.x = b for the following A & b:
011100100101    0
000111011100    1
111101000011    1
010000111110    1
110011110000    1
101100100100    1
011010110010    0
010010000111    1
101110110001    0
001100101110    1
100000011010    1
111111010100    1
Number of equations in system:   12
Rank of the matrix A:            11
Number of free variables:        1
Number of solutions to A.x = b:  2
The echelon forms of A & b are:
100000000000    1
010000000000    0
001000000000    1
000100000000    0
000010000100    0
000001000000    0
000000100100    1
000000010000    1
000000001000    0
000000000010    1
000000000001    0
000000000000    0