#sparse #binary #matrix

sparse-bin-mat

A sparse implementation of a binary matrix optimized for row operations

21 releases

Uses new Rust 2021

0.7.0 Apr 6, 2022
0.6.2 Nov 25, 2021
0.6.1 Oct 7, 2021
0.6.0 Mar 17, 2021
0.3.0 Dec 7, 2020

#157 in Data structures

Download history 25/week @ 2022-04-22 171/week @ 2022-04-29 131/week @ 2022-05-06 364/week @ 2022-05-13 71/week @ 2022-05-20 129/week @ 2022-05-27 173/week @ 2022-06-03 3/week @ 2022-06-10 6/week @ 2022-06-17 5/week @ 2022-06-24 23/week @ 2022-07-01 23/week @ 2022-07-08 25/week @ 2022-07-15 66/week @ 2022-07-22 4/week @ 2022-07-29 48/week @ 2022-08-05

143 downloads per month
Used in ldpc

MIT/Apache

110KB
2K SLoC

Sparse Bin Mat

A sparse implementation of a binary matrix optimized for row operations.

All elements in a binary matrix are element of the binary field GF2. That is, they are either 0 or 1 and addition is modulo 2.

Quick start

To instanciate a matrix, you need to specify the number of columns as well as the position of 1 in each rows.

use sparse_bin_mat::SparseBinMat;

// This is the matrix
// 1 0 1 0 1
// 0 1 0 1 0
// 0 0 1 0 0
let matrix = SparseBinMat::new(5, vec![vec![0, 2, 4], vec![1, 3], vec![2]]);

It is easy to access elements or rows of a matrix. However, since the matrix are optimized for row operations, you need to transpose the matrix if you want to perform column operations.

let matrix = SparseBinMat::new(5, vec![vec![0, 2, 4], vec![1, 3], vec![2]]);
assert_eq!(matrix.row(1), Some([1, 3].as_ref()));
assert_eq!(matrix.get(0, 0), Some(1));
assert_eq!(matrix.get(0, 1), Some(0));
// The element (0, 7) is out of bound for a 3 x 5 matrix.
assert_eq!(matrix.get(0, 7), None);

Adition and multiplication are implemented between matrix references.

let matrix = SparseBinMat::new(3, vec![vec![0, 1], vec![1, 2], vec![0, 2]]);
let identity = SparseBinMat::identity(3);

let sum = SparseBinMat::new(3, vec![vec![1], vec![2], vec![0]]);
assert_eq!(&matrix + &identity, sum);

assert_eq!(&matrix * &identity, matrix);

Many useful operations and decompositions are implemented. These include, but are not limited to

  • rank,
  • echelon from,
  • normal form,
  • tranposition,
  • horizontal and vertical concatenations,
  • and more ...

Operations are implemented as I need them, feel welcome to raise an issue if you need a new functionnality.

Dependencies

~1–1.7MB
~38K SLoC