Multiplication of `BitMatrix`s for linear algebra modulo 2

General Usage Performance
8

I have a small package for linear algebra mod 2, called Modulo2.jl. With this package, matrix multiplication mod 2 is actually faster than with floats:

julia> n = 2^14; a = Modulo2.randomarray(n, n); b = Modulo2.randomarray(n, n); @time a * b;
 35.638093 seconds (3 allocations: 32.000 MiB)

julia> n = 2^14; a = rand(n, n); b = rand(n, n); @time a * b;
 43.566516 seconds (2 allocations: 2.000 GiB, 0.27% gc time)

This seems to be about 2.8 times faster than @Oscar_Smith’s (quickly written) solution.

The package provides a type ZZ2 for integers mod 2 and ZZ2Array (ZZ2Vector, ZZ2Matrix) for packed, padded arrays. Apart from basic matrix operations it has functions related to Gaussian elimination (rref, rank, inv, det) as well as some support for broadcasting.

The package is not yet in the registry, so one needs to install it via

pkg> add https://github.com/matthias314/Modulo2.jl

So far, the only documentation is via docstrings.

UPDATE: Modulo2.jl is now available from the registry.

3 Likes