Package org.apache.sysds.runtime.data

Class SparseBlock

java.lang.Object

org.apache.sysds.runtime.data.SparseBlock

All Implemented Interfaces:

Serializable

Direct Known Subclasses:

SparseBlockCOO, SparseBlockCSR, SparseBlockMCSR

public abstract class SparseBlock
extends Object
implements Serializable

This SparseBlock is an abstraction for different sparse matrix formats. Since the design is a tradeoff between performance and generality, we restrict this abstraction to row-major sparse representations for now. All sparse matrix block operations are supposed to be implemented against this abstraction in order to enable variability/extensibility. Example sparse format that can be implemented efficiently include CSR, MCSR, and - with performance drawbacks - COO.

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	SparseBlock.Type

Constructor Summary

Constructors

Constructor	Description
SparseBlock()

Method Summary

Modifier and Type	Method	Description
abstract boolean	add(int r, int c, double v)	Add a value to a matrix cell (r,c).
abstract void	allocate(int r)	Allocate the underlying data structure holding non-zero values of row r if necessary.
abstract void	allocate(int r, int nnz)	Allocate the underlying data structure holding non-zero values of row r if necessary, w/ given size.
abstract 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.
abstract void	append(int r, int c, double v)	Append a value to the end of the physical representation.
abstract boolean	checkValidity(int rlen, int clen, long nnz, boolean strict)	Validate the correctness of the internal data structures of the different sparse block implementations.
abstract void	compact(int r)	Re-allocate physical row if physical size exceeds logical size plus resize factor.
abstract void	deleteIndexRange(int r, int cl, int cu)	Deletes all non-zero values of the given column range [cl,cu) in row r.
abstract SparseRow	get(int r)	Get values of row r in the format of a sparse row.
abstract double	get(int r, int c)	Get value of matrix cell (r,c).
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).
abstract int[]	indexes(int r)	Get the sorted array of column indexes of all non-zero entries in row r.
boolean	isAligned(int r, SparseBlock that)	Indicates if all non-zero values of row r are aligned with the same row of the given second sparse block instance, which can be exploited for more efficient operations.
boolean	isAligned(SparseBlock that)	Indicates if all non-zero values are aligned with the given second sparse block instance, which can be exploited for more efficient operations.
abstract boolean	isAllocated(int r)	Indicates if the underlying data structure for a given row is already allocated.
abstract boolean	isContiguous()	Indicates if the underlying data structures returned by values and indexes are contiguous arrays, which can be exploited for more efficient operations.
abstract boolean	isEmpty(int r)	Get information if row r is empty, i.e., does not contain non-zero values.
abstract boolean	isThreadSafe()	Indicates if the underlying implementation allows thread-safe row updates if concurrent threads update disjoint rows.
abstract int	numRows()	Get the number of rows in the sparse block.
abstract int	pos(int r)	Get the starting position of row r in the indexes/values arrays returned by indexes(r) and values(r).
abstract int	posFIndexGT(int r, int c)	Get position of first column index greater than column c in row r.
abstract int	posFIndexGTE(int r, int c)	Get position of first column index greater than or equal column c in row r.
abstract int	posFIndexLTE(int r, int c)	Get position of first column index lower than or equal column c in row r.
abstract void	reset()	Clears the sparse block by deleting non-zero values.
abstract void	reset(int ennz, int maxnnz)	Clears the sparse block by deleting non-zero values.
abstract void	reset(int r, int ennz, int maxnnz)	Clears row r of the sparse block by deleting non-zero values.
abstract boolean	set(int r, int c, double v)	Set the value of a matrix cell (r,c).
abstract void	set(int r, SparseRow row, boolean deep)	Set the values of row r to the given sparse row.
abstract 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.
abstract 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.
abstract long	size()	Get the number of non-zero values in the sparse block.
abstract int	size(int r)	Get the number of non-zero values in row r.
abstract long	size(int rl, int ru)	Get the number of non-zeros values in the row range of [rl, ru).
abstract 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);
abstract void	sort()	Sort all non-zero value/index pairs of the sparse block by row and column index.
abstract void	sort(int r)	Sort all non-zero value/index pairs of row r column index.
abstract String	toString()
abstract double[]	values(int r)	Get the array of all non-zero entries in row r, sorted by their column indexes.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

SparseBlock

public SparseBlock()

Method Detail

allocate

public abstract void allocate(int r)

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

Parameters:

r - row index

allocate

public abstract void allocate(int r,
                              int nnz)

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

Parameters:

r - row index

nnz - number of non-zeros

allocate

public abstract 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.

Parameters:

r - row index

ennz - estimated non-zeros

maxnnz - max non-zeros

compact

public abstract void compact(int r)

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

Parameters:

r - row index

numRows

public abstract int numRows()

Get the number of rows in the sparse block.

Returns:

number of rows

isThreadSafe

public abstract boolean isThreadSafe()

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

Returns:

true if thread-safe row updates

isContiguous

public abstract boolean isContiguous()

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

Returns:

true if underlying data structures are contiguous arrays

isAligned

public boolean isAligned(SparseBlock that)

Indicates if all non-zero values are aligned with the given second sparse block instance, which can be exploited for more efficient operations. Two non-zeros are aligned if they have the same column index and reside in the same array position.

Parameters:

that - sparse block

Returns:

true if all non-zero values are aligned with the given second sparse block

isAligned

public boolean isAligned(int r,
                         SparseBlock that)

Indicates if all non-zero values of row r are aligned with the same row of the given second sparse block instance, which can be exploited for more efficient operations. Two non-zeros are aligned if they have the same column index and reside in the same array position.

Parameters:

r - row index starting at 0

that - sparse block

Returns:

true if all non-zero values of row r are aligned with the same row of the given second sparse block instance

isAllocated

public abstract boolean isAllocated(int r)

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

Parameters:

r - row index

Returns:

true if already allocated

reset

public abstract void reset()

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

reset

public abstract 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.

Parameters:

ennz - estimated non-zeros

maxnnz - max non-zeros

reset

public abstract 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.

Parameters:

r - row index

ennz - estimated non-zeros

maxnnz - max non-zeros

size

public abstract long size()

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

Returns:

number of non-zero values in sparse block

size

public abstract int size(int r)

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

Parameters:

r - row index starting at 0

Returns:

number of non-zero values in row r

size

public abstract long size(int rl,
                          int ru)

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

Parameters:

rl - row lower index

ru - row upper index

Returns:

number of non-zero values in the row range

size

public abstract 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);

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 abstract 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.

Parameters:

r - row index starting at 0

Returns:

true if row does not contain non-zero values

checkValidity

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

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

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.

indexes

public abstract 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)).

Parameters:

r - row index starting at 0

Returns:

sorted array of column indexes

values

public abstract 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)).

Parameters:

r - row index starting at 0

Returns:

array of all non-zero entries in row r sorted by column indexes

pos

public abstract int pos(int r)

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

Parameters:

r - row index starting at 0

Returns:

starting position of row r

set

public abstract 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.

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 abstract 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.

Parameters:

r - row index starting at 0

row - sparse row

deep - indicator to create deep copy of sparse row

add

public abstract 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.

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 abstract 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.

Parameters:

r - row index starting at 0

c - column index starting at 0

v - zero or non-zero value

setIndexRange

public abstract 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).

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 abstract 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.

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 abstract void deleteIndexRange(int r,
                                      int cl,
                                      int cu)

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

Parameters:

r - row index starting at 0

cl - lower column index starting at 0

cu - upper column index starting at 0

sort

public abstract void sort()

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

sort

public abstract void sort(int r)

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

Parameters:

r - row index starting at 0

get

public abstract double get(int r,
                           int c)

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

Parameters:

r - row index starting at 0

c - column index starting at 0

Returns:

value of cell at position (r,c)

get

public abstract SparseRow get(int r)

Get values of row r in the format of a sparse row. NOTE: This method exists for incremental runtime integration and might be deleted in the future.

Parameters:

r - row index starting at 0

Returns:

values of row r as a sparse row

posFIndexLTE

public abstract 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.

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 abstract 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.

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 abstract 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.

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.

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.

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.

Parameters:

rl - inclusive lower row index starting at 0

ru - exclusive upper row index starting at 0

Returns:

IJV iterator

toString

public abstract String toString()

Overrides:

toString in class Object