pub struct BitGauss<Word: Unsigned = usize> { /* private fields */ }Expand description
§The BitGauss Type
§Introduction
BitGauss is a Gaussian elimination solver for systems of linear equations over GF(2):
A.x = bwhere A is an n x n square bit-matrix, b is the known right-hand side vector or length n, and x is the vector of unknowns of length n to be solved for.
On construction, a BitGauss object captures copies of A and b.
Then, it uses elementary row operations to transform the left-hand side matrix to reduced row echelon form while simultaneously performing 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.x = b, the BitGauss object can be queried for other helpful information, such as the rank of A, whether the system is consistent (i.e., whether any solutions exist), and so on.
See the complete list below.
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 only two values.
Therefore, over GF(2) the number of solutions is 0, 1, or 2^f, where f is the number of free variables.
If the system is consistent, then we can index the solutions by an integer i such that 0 <= i < 2^f.
- The
BitGauss::xmethod returns a random solution. - The
BitGauss::ximethod returns “the” solution indexedi.
For underdetermined systems, the “indexing” is something convenient and consistent across runs but not unique.
§Example
use gf2::*;
let mat: BitMat = BitMat::ones(4, 4);
let b: BitVec = BitVec::ones(4);
let solver: BitGauss = BitGauss::new(&mat, &b);
println!("The matrix:\n{}", mat);
println!("Matrix rank: {}", solver.rank());
println!("The `b` vector: {}", b.to_pretty_string());
println!("Solution count: {}", solver.solution_count());
println!("Number of free variables: {}", solver.free_count());
println!("Under-determined system? {}", solver.is_underdetermined());
println!("Consistent system? {}", solver.is_consistent());
println!("Solutions:");
for i in 0..solver.solution_count() {
println!("x({}): {}", i, solver.xi(i).unwrap().to_pretty_string());
}§Output
The matrix:
│1 1 1 1│
│1 1 1 1│
│1 1 1 1│
│1 1 1 1│
Matrix rank: 1
The `b` vector: [1 1 1 1]
Solution count: 8
Number of free variables: 3
Under-determined system? true
Consistent system? true
Solutions:
x(0): [1 0 0 0]
x(1): [0 1 0 0]
x(2): [0 0 1 0]
x(3): [1 1 1 0]
x(4): [0 0 0 1]
x(5): [1 1 0 1]
x(6): [1 0 1 1]
x(7): [0 1 1 1]§Method Summary
We have the following methods available on BitGauss objects:
| Method | Description |
|---|---|
BitGauss::new | Constructs a new BitGauss solver from a given bit-matrix A and bit-vector b. |
BitGauss::rank | Returns the rank of the matrix A. |
BitGauss::is_consistent | Returns true if the system is consistent (i.e., has at least one solution). |
BitGauss::is_underdetermined | Returns true if the system is underdetermined (i.e., has more variables than independent equations). |
BitGauss::free_count | Returns the number of free variables in the system. |
BitGauss::solution_count | Returns the total number of solutions to the system. |
BitGauss::x | Returns a random solution vector x if the system is consistent, or None if it is not. |
BitGauss::xi | Returns the solution vector x indexed by i if the system is consistent. |
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 only two values.
Therefore, over GF(2) the number of solutions is 0, 1, or 2^f, where f is the number of free variables.
If more than one solution exists, the BitGauss::x method returns one of them at random, while the BitGauss::xi method returns a specific solution indexed by a parameter i.
§See Also
Implementations§
Source§impl<Word: Unsigned> BitGauss<Word>
impl<Word: Unsigned> BitGauss<Word>
Sourcepub fn new(A: &BitMat<Word>, b: &BitVec<Word>) -> Self
pub fn new(A: &BitMat<Word>, b: &BitVec<Word>) -> Self
Constructs a new BitGauss struct where we are solving the system of linear equations A.x = b.
§Panics
Panics if the A matrix is not square or if the A matrix and b vector have a different number of rows.
§Examples
use gf2::*;
let A: BitMat = BitMat::from_string("111 111 111").unwrap();
let b: BitVec = BitVec::from_string("111").unwrap();
let solver: BitGauss = BitGauss::new(&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);Sourcepub fn rank(&self) -> usize
pub fn rank(&self) -> usize
Returns the rank of the matrix A.
§Examples
use gf2::*;
let A: BitMat = BitMat::from_string("111 111 111").unwrap();
let b: BitVec = BitVec::from_string("111").unwrap();
let solver: BitGauss = BitGauss::new(&A, &b);
assert_eq!(solver.rank(), 1);Sourcepub fn free_count(&self) -> usize
pub fn free_count(&self) -> usize
Returns the number of free variables in the system.
§Examples
use gf2::*;
let A: BitMat = BitMat::from_string("111 111 111").unwrap();
let b: BitVec = BitVec::from_string("111").unwrap();
let solver: BitGauss = BitGauss::new(&A, &b);
assert_eq!(solver.free_count(), 2);Sourcepub fn is_underdetermined(&self) -> bool
pub fn is_underdetermined(&self) -> bool
Returns true if the system is underdetermined.
§Examples
use gf2::*;
let A: BitMat = BitMat::from_string("111 111 111").unwrap();
let b: BitVec = BitVec::from_string("111").unwrap();
let solver: BitGauss = BitGauss::new(&A, &b);
assert_eq!(solver.is_underdetermined(), true);Sourcepub fn is_consistent(&self) -> bool
pub fn is_consistent(&self) -> bool
Returns true if the system of linear equations A.x = b is consistent.
A system is consistent if there is at least one solution.
§Examples
use gf2::*;
let A: BitMat = BitMat::from_string("111 111 111").unwrap();
let b: BitVec = BitVec::from_string("111").unwrap();
let solver: BitGauss = BitGauss::new(&A, &b);
assert!(solver.is_consistent());Sourcepub fn x(&self) -> Option<BitVec<Word>>
pub fn x(&self) -> Option<BitVec<Word>>
Returns a solution to the system of linear equations A.x = b or None 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.
§Examples
use gf2::*;
let A: BitMat = BitMat::identity(3);
let b: BitVec = BitVec::from_string("111").unwrap();
let solver: BitGauss = BitGauss::new(&A, &b);
assert_eq!(solver.x().unwrap().to_string(), "111");Sourcepub fn solution_count(&self) -> usize
pub fn solution_count(&self) -> usize
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(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).
§Examples
use gf2::*;
let A: BitMat = BitMat::from_string("111 111 111").unwrap();
let b: BitVec = BitVec::from_string("111").unwrap();
let solver: BitGauss = BitGauss::new(&A, &b);
assert_eq!(solver.solution_count(), 4);Sourcepub fn xi(&self, i: usize) -> Option<BitVec<Word>>
pub fn xi(&self, i: usize) -> Option<BitVec<Word>>
Returns the ith solution to the system of linear equations A.x = b or None if the system is
inconsistent or if i is out of bounds.
If the system is consistent and determined, then there is a unique solution and xi(0) is the same as
x().
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.
§Examples
use gf2::*;
let A: BitMat = BitMat::from_string("111 111 111").unwrap();
let b: BitVec = BitVec::from_string("111").unwrap();
let solver: BitGauss = BitGauss::new(&A, &b);
assert_eq!(solver.solution_count(), 4);
assert_eq!(solver.xi(0).unwrap().to_string(), "100", "xi(0) = 100");
assert_eq!(solver.xi(1).unwrap().to_string(), "010", "xi(1) = 010");
assert_eq!(solver.xi(2).unwrap().to_string(), "001", "xi(2) = 001");
assert_eq!(solver.xi(3).unwrap().to_string(), "111", "xi(3) = 111");
let A: BitMat = BitMat::identity(3);
let solver: BitGauss = BitGauss::new(&A, &b);
assert_eq!(solver.solution_count(), 1);
assert_eq!(solver.xi(0).unwrap().to_string(), "111", "xi(0) = 111");