sparse-binary-matrix
A javascript library for handling sparse binary matrices. This library provides methods to efficiently store sparse binary matrices and operate computations on them. This module is available on npm as sparse-binary-matrix.
This library has been designed in an idea to improve space complexity when storing those matrices. A simple matrix of size (m, n) holds m*n coefficients. Assuming all the matrices are binary (a coefficient can only be 1 or 0), it can store matrices using only d*m*n < m*n coefficients, with 0 < d < 1 being the density of the matrix.
install
If you're using node.js and npm, type into a terminal :
$ npm install sparse-binary-matrix --save
If you're using the browser, add to the beginning of your file:
example
var sbm = // create a random sparse matrix of size 100x100 and density of 0.2sbm
api
The following methods are available:
make
var dimension = x: number of lines y: number of columnsvar matrix = sbm
Creates a sparse binary matrix from the given source : it can be a predicate depending on (i, j), or a line-based binary matrix. You need to specify the dimension only if you provide a predicate as source.
The time complexity of this method is O(xy)
matrix
var matrix = sbm
Returns the row-based binary matrix corresponding to the given sparse matrix.
The time complexity of this method is O(xy)
check
sbm
Returns true if the coefficient of the matrix (i, j) is true.
The time complexity of this method is O(xy)
equal
sbm
Returns true if the matrices are equal.
The time complexity of this method is O(xy²log(y))
identity
var id = sbm
Returns the identity matrix of dimension n.
The time complexity of this method is O(n)
zero
var zero = sbm
Returns a (x, y) dimension matrix full of zeros. If only one argument is specified, the matrix will be square.
The time complexity of this method is O(x)
one
var one = sbm
Returns a (x, y) dimension matrix full of ones. If only one argument is specified, the matrix will be square.
The time complexity of this method is O(xy)
transpose
var Tmatrix = sbm
Transposes the given matrix.
The time complexity of this method is O(x²y)
trace
var tr = sbm
Returns the trace of the given matrix.
The time complexity of this method is O(n²) (x = y = n)
complement, not
var matrix = sbm = sbm
Returns the matrix not(M), where not(M)[i, j] is true if and only if M[i, j] is false.
The time complexity of this method is O(xy)
and
The time complexity of this method is O(xy)
or
The time complexity of this method is O(xy)
xor, add
var matrix = sbm = sbm
Returns the sum of both matrices.
The time complexity of this method is O(xy)
multiply
var matrix = sbm
Returns the product of both matrices.
The time complexity of this method is O((x+y)xy²)
pow
var matrix = sbm
Returns the given matrix to power n.
The time complexity of this method is O((x+y)xy²*log(n))
isSymmetric
var is = sbm
Returns true if the matrix is symmetric.
The time complexity of this method is O(x²y²)
popcount
var cnt = sbm
Returns the number of true coefficients inside the given matrix.
The time complexity of this method is O(xy)
density
var density = sbm
Returns the density of the matrix, that is the ratio of true (=1) coefficients over the number of total possible true coefficients for the matrix.
The time complexity of this method is O(xy)
release History
- 0.1.0 Initial release