Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 BitStringRowReduce

Source Notebook

A memory efficient form of Gaussian elimination to row echelon form modulo 2

Contributed by: Daniel Lichtblau

ResourceFunction["BitStringRowReduce"][{n1,n2,…},ncols]

treats the integers ni as vectors of zeros and ones, each having ncols bits, and does row reduction using mod 2 arithmetic.

Details and Options

The resulting integers represent bit strings that correspond to the reduced echelon form one would obtain using RowReduce with the option setting Modulus→2 on the bit vectors that correspond to the input.
The number of columns must be made explicit since there might be leading zeros in all rows.
The first nonzero bit in each result integer corresponds to a pivot position so the integers in the result will be strictly decreasing in value.
ResourceFunction["BitStringRowReduce"] 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) 

Reduce a list of integers bit-wise:

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

Create a random matrix of bit vectors:

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

Now reduce it:

In[7]:=
redvecs = ResourceFunction["BitStringRowReduce"][bitvecs,]
Out[7]=

Scope (2) 

Create a large array of long integers:

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

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

In[9]:=
Timing[bigredvecs = ResourceFunction["BitStringRowReduce"][bigbitvecs, bigncols];]
Out[9]=

Properties and Relations (2) 

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

In[10]:=
mat
Out[10]=

Use RowReduce modulo 2 to put it into echelon form:

In[11]:=
redmat = RowReduce[mat, Modulus -> 2]
Out[11]=

Check that this agrees with the result from BitStringRowReduce:

In[12]:=
Map[IntegerDigits[#, 2, ncols] &, redvecs] === redmat
Out[12]=

Create a matrix of 0‐1 vectors corresponding to the larger integers:

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

RowReduce is substantially slower as compared to BitStringRowReduce:

In[14]:=
Timing[bigredmat = RowReduce[bigmat, Modulus -> 2];]
Out[14]=

Again, check that the results are equivalent:

In[15]:=
Map[IntegerDigits[#, 2, bigncols] &, bigredvecs] === bigredmat
Out[15]=

Here are the sizes in bytes of the input and result using the bit string approach:

In[16]:=
Map[ByteCount, {bigbitvecs, bigredvecs}]
Out[16]=

Here are the corresponding sizes in bytes of the input and result when using an explicit matrix:

In[17]:=
Map[ByteCount, {bigmat, bigredmat}]
Out[17]=

Requirements

Wolfram Language 11.3 (March 2018) or above

Version History

  • 1.0.0 – 03 April 2019

Related Resources

License Information