Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 BitStringLinearSolve

Source Notebook

A memory efficient form of solving linear systems modulo 2

Contributed by: Daniel Lichtblau

ResourceFunction["BitStringLinearSolve"][{n1,n2,…},rhs,ncols]]

solves the linear system {n1,n2,…}.x=rhs where {n1,n2,…} is a list of integers corresponding to bit vectors of length ncols, and rhs is an explicit vector of zeros and ones.

Details and Options

The result is a 0‐1 vector corresponding to the solution one would obtain using LinearSolve with the option setting Modulus→2 on the bit vectors that correspond to the matrix.
If no solution exists, ResourceFunction["BitStringLinearSolve"] will return an empty list.
ResourceFunction["BitStringLinearSolve"] returns one solution. Others may be found by adding multiples of null vectors mod 2 that may be computed using the resource function BitStringNullSpace.
The number of columns must be made explicit to account for the possibility of leading zeros in all rows.
ResourceFunction["BitStringLinearSolve"] is intended for dense linear algebra. Sparse methods might be better suited for linear algebra modulo 2 when most matrix entries are zeros.

Examples

Basic Examples (2) 

Solve a simple example for a bit vector:

In[1]:=
ResourceFunction["BitStringLinearSolve"][{1, 2, 3, 4}, {1, 0, 1, 0}, 3]
Out[1]=

Create a random matrix of bit vectors and a random right hand side:

In[2]:=
SeedRandom[1111]; nrows = 7; ncols = 9; mat = RandomInteger[{0, 1}, {nrows, ncols}] bitvecs = Map[FromDigits[#, 2] &, mat]; rhs = RandomInteger[{0, 1}, nrows];
Out[5]=

Solve the corresponding linear system modulo 2:

In[6]:=
bitsoln = ResourceFunction["BitStringLinearSolve"][bitvecs, rhs, ncols]
Out[6]=

Scope (2) 

Create a large array of bit strings to use as a matrix, along with a suitable right hand side vector:

In[7]:=
SeedRandom[1111]; bignrows = 1777; bigncols = 1789; bigbitvecs = Table[FromDigits[RandomInteger[{0, 1}, bigncols], 2], bignrows]; bigrhs = RandomInteger[{0, 1}, bignrows];

BitStringLinearSolve is especially useful when working with matrices that might otherwise require excessive memory:

In[8]:=
Timing[bigbitsol = ResourceFunction["BitStringLinearSolve"][bigbitvecs, bigrhs, bigncols];]
Out[8]=

Properties and Relations (5) 

Here is the matrix from which the bit vectors were created:

In[9]:=
mat
Out[9]=

We see that the prior result agrees with LinearSolve:

In[10]:=
LinearSolve[mat, rhs, Modulus -> 2]
Out[10]=
In[11]:=
% == bitsoln
Out[11]=

Similarly, create a matrix of explicit 0‐1 vectors corresponding to the large integers:

In[12]:=
bigmat = Map[IntegerDigits[#, 2, bigncols] &, bigbitvecs];

LinearSolve is substantially slower as compared to BitStringLinearSolve:

In[13]:=
Timing[bigbitsol2 = LinearSolve[bigmat, bigrhs, Modulus -> 2];]
Out[13]=

Check that the results are the same:

In[14]:=
bigbitsol2 === bigbitsol
Out[14]=

Requirements

Wolfram Language 11.3 (March 2018) or above

Version History

  • 1.0.0 – 03 April 2019

Related Resources

License Information