sparse-binary-matrix

    0.1.2 • Public • Published

    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:

    <script src="sbm.js"></script>

    example

    var sbm = require('sparse-binary-matrix')
     
    // create a random sparse matrix of size 100x100 and density of 0.2
    sbm.make(function() { return Math.random() < 0.2 }, { x:100, y:100 })

    api

    The following methods are available:

    make

    var dimension = {x: [number of lines], y: [number of columns]}
    var matrix = sbm.make(source, dimension)

    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.make(sparsematrix)

    Returns the row-based binary matrix corresponding to the given sparse matrix.

    The time complexity of this method is O(xy)

    check

    sbm.check(matrix, i, j)

    Returns true if the coefficient of the matrix (i, j) is true.

    The time complexity of this method is O(xy)

    equal

    sbm.equal(matrixA, matrixB)

    Returns true if the matrices are equal.

    The time complexity of this method is O(xy²log(y))

    identity

    var id = sbm.identity(n)

    Returns the identity matrix of dimension n.

    The time complexity of this method is O(n)

    zero

    var zero = sbm.zero(x, y)

    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.one(x, y)

    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.transpose(matrix)

    Transposes the given matrix.

    The time complexity of this method is O(x²y)

    trace

    var tr = sbm.trace(matrix)

    Returns the trace of the given matrix.

    The time complexity of this method is O(n²) (x = y = n)

    complement, not

    var matrix = sbm.not(matrix)
               = sbm.complement(matrix)

    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.xor(mA, mB)
               = sbm.add(mA, mB)

    Returns the sum of both matrices.

    The time complexity of this method is O(xy)

    multiply

    var matrix = sbm.multiply(mA, mB)

    Returns the product of both matrices.

    The time complexity of this method is O((x+y)xy²)

    pow

    var matrix = sbm.pow(matrix, n)

    Returns the given matrix to power n.

    The time complexity of this method is O((x+y)xy²*log(n))

    isSymmetric

    var is = sbm.isSymmetric(matrix)

    Returns true if the matrix is symmetric.

    The time complexity of this method is O(x²y²)

    popcount

    var cnt = sbm.popcount(matrix)

    Returns the number of true coefficients inside the given matrix.

    The time complexity of this method is O(xy)

    density

    var density = sbm.density(matrix)

    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

    license

    MIT

    Install

    npm i sparse-binary-matrix

    DownloadsWeekly Downloads

    1

    Version

    0.1.2

    License

    none

    Last publish

    Collaborators

    • ilambda