#sparse #binary #matrix

sparse-bin-mat

A sparse implementation of a binary matrix optimized for row operations

20 releases

new 0.6.2 Nov 25, 2021
0.6.1 Oct 7, 2021
0.6.0 Mar 17, 2021
0.5.2 Feb 25, 2021
0.1.0 Dec 1, 2020

#455 in Data structures

Download history 5/week @ 2021-08-09 36/week @ 2021-08-16 11/week @ 2021-08-23 1/week @ 2021-09-06 18/week @ 2021-09-13 11/week @ 2021-09-20 18/week @ 2021-09-27 16/week @ 2021-10-04 44/week @ 2021-10-11 13/week @ 2021-10-18 2/week @ 2021-10-25 2/week @ 2021-11-01 19/week @ 2021-11-08 2/week @ 2021-11-15 25/week @ 2021-11-22

53 downloads per month
Used in ldpc

MIT/Apache

98KB
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.3–2MB
~46K SLoC

ğa