Home Original page

SparseBlockCOO (Apache SystemDS 3.4.0-SNAPSHOT API)

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(int r, int c, double v)

      Add a value to a matrix cell (r,c).
      void allocate​(int r)

      Allocate the underlying data structure holding non-zero values of row r if necessary.
      void allocate​(int r, int nnz)

      Allocate the underlying data structure holding non-zero values of row r if necessary, w/ given size.
      void allocate​(int r, int ennz, int maxnnz)

      Allocate the underlying data structure holding non-zero values of row r w/ the specified estimated nnz and max nnz.
      void append​(int r, int c, double v)

      Append a value to the end of the physical representation.
      boolean checkValidity​(int rlen, int clen, long nnz, boolean strict)

      Validate the correctness of the internal data structures of the different sparse block implementations.
      void compact​(int r)

      Re-allocate physical row if physical size exceeds logical size plus resize factor.
      void deleteIndexRange​(int r, int cl, int cu)

      Deletes all non-zero values of the given column range [cl,cu) in row r.
      static long estimateSizeInMemory​(long nrows, long ncols, double sparsity)

      Get the estimated in-memory size of the sparse block in COO with the given dimensions w/o accounting for overallocation.
      SparseRow get​(int r)

      Get values of row r in the format of a sparse row.
      double get​(int r, int c)

      Get value of matrix cell (r,c).
      long getExactSizeInMemory()

      Computes the exact size in memory of the materialized block
      Iterator<IJV> getIterator()

      Get a non-zero iterator over the entire sparse block.
      Iterator<IJV> getIterator​(int ru)

      Get a non-zero iterator over the partial sparse block [0,ru).
      Iterator<IJV> getIterator​(int rl, int ru)

      Get a non-zero iterator over the subblock [rl, ru).
      Iterator<Integer> getNonEmptyRowsIterator​(int rl, int ru)  
      int[] indexes()

      Get raw access to underlying array of column indices For use in GPU code
      int[] indexes​(int r)

      Get the sorted array of column indexes of all non-zero entries in row r.
      boolean isAllocated​(int r)

      Indicates if the underlying data structure for a given row is already allocated.
      boolean isContiguous()

      Indicates if the underlying data structures returned by values and indexes are contiguous arrays, which can be exploited for more efficient operations.
      boolean isEmpty​(int r)

      Get information if row r is empty, i.e., does not contain non-zero values.
      boolean isThreadSafe()

      Indicates if the underlying implementation allows thread-safe row updates if concurrent threads update disjoint rows.
      int numRows()

      Get the number of rows in the sparse block.
      int pos​(int r)

      Get the starting position of row r in the indexes/values arrays returned by indexes(r) and values(r).
      int posFIndexGT​(int r, int c)

      Get position of first column index greater than column c in row r.
      int posFIndexGTE​(int r, int c)

      Get position of first column index greater than or equal column c in row r.
      int posFIndexLTE​(int r, int c)

      Get position of first column index lower than or equal column c in row r.
      void reset()

      Clears the sparse block by deleting non-zero values.
      void reset​(int ennz, int maxnnz)

      Clears the sparse block by deleting non-zero values.
      void reset​(int r, int ennz, int maxnnz)

      Clears row r of the sparse block by deleting non-zero values.
      int[] rowIndexes()

      Get raw access to underlying array of row indices For use in GPU code
      boolean set​(int r, int c, double v)

      Set the value of a matrix cell (r,c).
      void set​(int r, SparseRow row, boolean deep)

      Set the values of row r to the given sparse row.
      void setIndexRange​(int r, int cl, int cu, double[] v, int[] vix, int vpos, int vlen)

      Sets a sparse array of non-zeros values and indexes into the column range [cl,cu) in row r.
      void setIndexRange​(int r, int cl, int cu, double[] v, int vix, int vlen)

      Sets a dense array of non-zeros values into the column range [cl,cu) in row r.
      long size()

      Get the number of non-zero values in the sparse block.
      int size​(int r)

      Get the number of non-zero values in row r.
      long size​(int rl, int ru)

      Get the number of non-zeros values in the row range of [rl, ru).
      long size​(int rl, int ru, int cl, int cu)

      Get the number of non-zeros values in the row and column range of [rl/cl, ru/cu);
      void sort()

      Sort all non-zero value/index pairs of the sparse block by row and column index.
      void sort​(int r)

      Sort all non-zero value/index pairs of row r column index.
      String toString()  
      double[] values()

      Get raw access to underlying array of values For use in GPU code
      double[] values​(int r)

      Get the array of all non-zero entries in row r, sorted by their column indexes.

    • Constructor Detail

      • SparseBlockCOO

        public SparseBlockCOO​(int rlen)

      • SparseBlockCOO

        public SparseBlockCOO​(int rlen,
                      int capacity)

      • SparseBlockCOO

        public SparseBlockCOO​(SparseBlock sblock)

        Copy constructor sparse block abstraction.

        Parameters:
        sblock - sparse block to copy

      • SparseBlockCOO

        public SparseBlockCOO​(SparseRow[] rows,
                      int nnz)

        Copy constructor old sparse row representation.

        Parameters:
        rows - array of sparse rows
        nnz - number of non-zeros

    • Method Detail

      • estimateSizeInMemory

        public static long estimateSizeInMemory​(long nrows,
                                        long ncols,
                                        double sparsity)

        Get the estimated in-memory size of the sparse block in COO with the given dimensions w/o accounting for overallocation.

        Parameters:
        nrows - number of rows
        ncols - number of columns
        sparsity - sparsity ratio
        Returns:
        memory estimate

      • getExactSizeInMemory

        public long getExactSizeInMemory()

        Computes the exact size in memory of the materialized block

        Specified by:
        getExactSizeInMemory in class SparseBlock
        Returns:
        the exact size in memory

      • allocate

        public void allocate​(int r)

        Allocate the underlying data structure holding non-zero values of row r if necessary.

        Specified by:
        allocate in class SparseBlock
        Parameters:
        r - row index

      • allocate

        public void allocate​(int r,
                     int nnz)

        Allocate the underlying data structure holding non-zero values of row r if necessary, w/ given size.

        Specified by:
        allocate in class SparseBlock
        Parameters:
        r - row index
        nnz - number of non-zeros

      • allocate

        public void allocate​(int r,
                     int ennz,
                     int maxnnz)

        Allocate the underlying data structure holding non-zero values of row r w/ the specified estimated nnz and max nnz.

        Specified by:
        allocate in class SparseBlock
        Parameters:
        r - row index
        ennz - estimated non-zeros
        maxnnz - max non-zeros

      • compact

        public void compact​(int r)

        Re-allocate physical row if physical size exceeds logical size plus resize factor.

        Specified by:
        compact in class SparseBlock
        Parameters:
        r - row index

      • numRows

        public int numRows()

        Get the number of rows in the sparse block.

        Specified by:
        numRows in class SparseBlock
        Returns:
        number of rows

      • isThreadSafe

        public boolean isThreadSafe()

        Indicates if the underlying implementation allows thread-safe row updates if concurrent threads update disjoint rows.

        Specified by:
        isThreadSafe in class SparseBlock
        Returns:
        true if thread-safe row updates

      • isContiguous

        public boolean isContiguous()

        Indicates if the underlying data structures returned by values and indexes are contiguous arrays, which can be exploited for more efficient operations.

        Specified by:
        isContiguous in class SparseBlock
        Returns:
        true if underlying data structures are contiguous arrays

      • isAllocated

        public boolean isAllocated​(int r)

        Indicates if the underlying data structure for a given row is already allocated.

        Specified by:
        isAllocated in class SparseBlock
        Parameters:
        r - row index
        Returns:
        true if already allocated

      • checkValidity

        public boolean checkValidity​(int rlen,
                             int clen,
                             long nnz,
                             boolean strict)

        Validate the correctness of the internal data structures of the different sparse block implementations.

        Specified by:
        checkValidity in class SparseBlock
        Parameters:
        rlen - number of rows
        clen - number of columns
        nnz - number of non zeros
        strict - enforce optional properties
        Returns:
        true if the sparse block is valid wrt the corresponding format such as COO, CSR, MCSR.

      • reset

        public void reset()

        Clears the sparse block by deleting non-zero values. After this call all size() calls are guaranteed to return 0.

        Specified by:
        reset in class SparseBlock

      • reset

        public void reset​(int ennz,
                  int maxnnz)

        Clears the sparse block by deleting non-zero values. After this call all size() calls are guaranteed to return 0.

        Specified by:
        reset in class SparseBlock
        Parameters:
        ennz - estimated non-zeros
        maxnnz - max non-zeros

      • reset

        public void reset​(int r,
                  int ennz,
                  int maxnnz)

        Clears row r of the sparse block by deleting non-zero values. After this call size(r) is guaranteed to return 0.

        Specified by:
        reset in class SparseBlock
        Parameters:
        r - row index
        ennz - estimated non-zeros
        maxnnz - max non-zeros

      • size

        public long size()

        Get the number of non-zero values in the sparse block.

        Specified by:
        size in class SparseBlock
        Returns:
        number of non-zero values in sparse block

      • size

        public int size​(int r)

        Get the number of non-zero values in row r.

        Specified by:
        size in class SparseBlock
        Parameters:
        r - row index starting at 0
        Returns:
        number of non-zero values in row r

      • size

        public long size​(int rl,
                 int ru)

        Get the number of non-zeros values in the row range of [rl, ru).

        Specified by:
        size in class SparseBlock
        Parameters:
        rl - row lower index
        ru - row upper index
        Returns:
        number of non-zero values in the row range

      • size

        public long size​(int rl,
                 int ru,
                 int cl,
                 int cu)

        Get the number of non-zeros values in the row and column range of [rl/cl, ru/cu);

        Specified by:
        size in class SparseBlock
        Parameters:
        rl - row lower index
        ru - row upper index
        cl - column lower index
        cu - column upper index
        Returns:
        number of non-zero values in the row and column range

      • isEmpty

        public boolean isEmpty​(int r)

        Get information if row r is empty, i.e., does not contain non-zero values. Equivalent to size(r)==0. Users should do this check if it is unknown if the underlying row data structure is allocated.

        Specified by:
        isEmpty in class SparseBlock
        Parameters:
        r - row index starting at 0
        Returns:
        true if row does not contain non-zero values

      • indexes

        public int[] indexes​(int r)

        Get the sorted array of column indexes of all non-zero entries in row r. Note that - for flexibility of the implementing format - the returned array may be larger, where the range for row r is given by [pos(r),pos(r)+size(r)).

        Specified by:
        indexes in class SparseBlock
        Parameters:
        r - row index starting at 0
        Returns:
        sorted array of column indexes

      • values

        public double[] values​(int r)

        Get the array of all non-zero entries in row r, sorted by their column indexes. Note that - for flexibility of the implementing format - the returned array may be larger, where the range for row r is given by [pos(r),pos(r)+size(r)).

        Specified by:
        values in class SparseBlock
        Parameters:
        r - row index starting at 0
        Returns:
        array of all non-zero entries in row r sorted by column indexes

      • pos

        public int pos​(int r)

        Get the starting position of row r in the indexes/values arrays returned by indexes(r) and values(r).

        Specified by:
        pos in class SparseBlock
        Parameters:
        r - row index starting at 0
        Returns:
        starting position of row r

      • set

        public boolean set​(int r,
                   int c,
                   double v)

        Set the value of a matrix cell (r,c). This might update an existing non-zero value, insert a new non-zero value, or delete a non-zero value.

        Specified by:
        set in class SparseBlock
        Parameters:
        r - row index starting at 0
        c - column index starting at 0
        v - zero or non-zero value
        Returns:
        true, if number of non-zeros changed

      • set

        public void set​(int r,
                SparseRow row,
                boolean deep)

        Set the values of row r to the given sparse row. This might update existing non-zero values, insert a new row, or delete a row. NOTE: This method exists for incremental runtime integration and might be deleted in the future.

        Specified by:
        set in class SparseBlock
        Parameters:
        r - row index starting at 0
        row - sparse row
        deep - indicator to create deep copy of sparse row

      • add

        public boolean add​(int r,
                   int c,
                   double v)

        Add a value to a matrix cell (r,c). This might update an existing non-zero value, or insert a new non-zero value.

        Specified by:
        add in class SparseBlock
        Parameters:
        r - row index starting at 0
        c - column index starting at 0
        v - zero or non-zero value
        Returns:
        true, if number of non-zeros changed

      • append

        public void append​(int r,
                   int c,
                   double v)

        Append a value to the end of the physical representation. This should only be used for operations with sequential write pattern or if followed by a sort() operation. Note that this operation does not perform any matrix cell updates.

        Specified by:
        append in class SparseBlock
        Parameters:
        r - row index starting at 0
        c - column index starting at 0
        v - zero or non-zero value

      • setIndexRange

        public void setIndexRange​(int r,
                          int cl,
                          int cu,
                          double[] v,
                          int vix,
                          int vlen)

        Sets a dense array of non-zeros values into the column range [cl,cu) in row r. The passed value array may be larger and the relevant range is given by [vix,vix+len).

        Specified by:
        setIndexRange in class SparseBlock
        Parameters:
        r - row index starting at 0
        cl - lower column index starting at 0
        cu - upper column index starting at 0
        v - value array
        vix - start index in value array
        vlen - number of relevant values

      • setIndexRange

        public void setIndexRange​(int r,
                          int cl,
                          int cu,
                          double[] v,
                          int[] vix,
                          int vpos,
                          int vlen)

        Sets a sparse array of non-zeros values and indexes into the column range [cl,cu) in row r. The passed value array may be larger.

        Specified by:
        setIndexRange in class SparseBlock
        Parameters:
        r - row index starting at 0
        cl - lower column index starting at 0
        cu - upper column index starting at 0
        v - value array
        vix - column index array
        vpos - start index in value and index arrays
        vlen - number of relevant values

      • deleteIndexRange

        public void deleteIndexRange​(int r,
                             int cl,
                             int cu)

        Deletes all non-zero values of the given column range [cl,cu) in row r.

        Specified by:
        deleteIndexRange in class SparseBlock
        Parameters:
        r - row index starting at 0
        cl - lower column index starting at 0
        cu - upper column index starting at 0

      • sort

        public void sort()

        Sort all non-zero value/index pairs of the sparse block by row and column index.

        Specified by:
        sort in class SparseBlock

      • sort

        public void sort​(int r)

        Sort all non-zero value/index pairs of row r column index.

        Specified by:
        sort in class SparseBlock
        Parameters:
        r - row index starting at 0

      • get

        public double get​(int r,
                  int c)

        Get value of matrix cell (r,c). In case of non existing values this call returns 0.

        Specified by:
        get in interface Block
        Specified by:
        get in class SparseBlock
        Parameters:
        r - row index starting at 0
        c - column index starting at 0
        Returns:
        value of cell at position (r,c)

      • get

        public SparseRow get​(int r)

        Get values of row r in the format of a sparse row.

        Specified by:
        get in class SparseBlock
        Parameters:
        r - row index starting at 0
        Returns:
        values of row r as a sparse row

      • posFIndexLTE

        public int posFIndexLTE​(int r,
                        int c)

        Get position of first column index lower than or equal column c in row r. The position is relative to the indexes/values arrays returned by indexes(r) and values(r). If no such value exists, this call returns -1.

        Specified by:
        posFIndexLTE in class SparseBlock
        Parameters:
        r - row index starting at 0
        c - column index starting at 0
        Returns:
        position of the first column index lower than or equal to column c in row r

      • posFIndexGTE

        public int posFIndexGTE​(int r,
                        int c)

        Get position of first column index greater than or equal column c in row r. The position is relative to the indexes/values arrays returned by indexes(r) and values(r). If no such value exists, this call returns -1. Note if CSR the pos(r) is subtracted from the result.

        Specified by:
        posFIndexGTE in class SparseBlock
        Parameters:
        r - row index starting at 0
        c - column index starting at 0
        Returns:
        position of the first column index greater than or equal to column c in row r

      • posFIndexGT

        public int posFIndexGT​(int r,
                       int c)

        Get position of first column index greater than column c in row r. The position is relative to the indexes/values arrays returned by indexes(r) and values(r). If no such value exists, this call returns -1.

        Specified by:
        posFIndexGT in class SparseBlock
        Parameters:
        r - row index starting at 0
        c - column index starting at 0
        Returns:
        position of the first column index greater than column c in row r

      • getIterator

        public Iterator<IJV> getIterator()

        Get a non-zero iterator over the entire sparse block. Note that the returned IJV object is reused across next calls and should be directly consumed or deep copied.

        Overrides:
        getIterator in class SparseBlock
        Returns:
        IJV iterator

      • getIterator

        public Iterator<IJV> getIterator​(int ru)

        Get a non-zero iterator over the partial sparse block [0,ru). Note that the returned IJV object is reused across next calls and should be directly consumed or deep copied.

        Overrides:
        getIterator in class SparseBlock
        Parameters:
        ru - exclusive upper row index starting at 0
        Returns:
        IJV iterator

      • getIterator

        public Iterator<IJV> getIterator​(int rl,
                                 int ru)

        Get a non-zero iterator over the subblock [rl, ru). Note that the returned IJV object is reused across next calls and should be directly consumed or deep copied.

        Overrides:
        getIterator in class SparseBlock
        Parameters:
        rl - inclusive lower row index starting at 0
        ru - exclusive upper row index starting at 0
        Returns:
        IJV iterator

      • rowIndexes

        public int[] rowIndexes()

        Get raw access to underlying array of row indices For use in GPU code

        Returns:
        array of row indices

      • indexes

        public int[] indexes()

        Get raw access to underlying array of column indices For use in GPU code

        Returns:
        array of column indices

      • values

        public double[] values()

        Get raw access to underlying array of values For use in GPU code

        Returns:
        array of values