Sparse
This implements sparse arrays of arbitrary dimension on top of numpy and scipy.sparse.
It generalizes the scipy.sparse.coo_matrix and scipy.sparse.dok_matrix layouts,
but extends beyond just rows and columns to an arbitrary number of dimensions.
Additionally, this project maintains compatibility with the numpy.ndarray interface
rather than the numpy.matrix interface used in scipy.sparse
These differences make this project useful in certain situations where scipy.sparse matrices are not well suited, but it should not be considered a full replacement. The data structures in pydata/sparse complement and can be used in conjunction with the fast linear algebra routines inside scipy.sparse. A format conversion or copy may be required.
Motivation
Sparse arrays, or arrays that are mostly empty or filled with zeros, are common in many scientific applications. To save space we often avoid storing these arrays in traditional dense formats, and instead choose different data structures. Our choice of data structure can significantly affect our storage and computational costs when working with these arrays.
Design
The main data structure in this library follows the Coordinate List (COO) layout for sparse matrices, but extends it to multiple dimensions.
The COO layout, which stores the row index, column index, and value of every element:
row |
col |
data |
|---|---|---|
0 |
0 |
10 |
0 |
2 |
13 |
1 |
3 |
9 |
3 |
8 |
21 |
It is straightforward to extend the COO layout to an arbitrary number of dimensions:
dim1 |
dim2 |
dim3 |
… |
data |
|---|---|---|---|---|
0 |
0 |
0 |
. |
10 |
0 |
0 |
3 |
. |
13 |
0 |
2 |
2 |
. |
9 |
3 |
1 |
4 |
. |
21 |
This makes it easy to store a multidimensional sparse array, but we still need to reimplement all of the array operations like transpose, reshape, slicing, tensordot, reductions, etc., which can be challenging in general.
This library also includes several other data structures. Similar to COO, the Dictionary of Keys (DOK) format for sparse matrices generalizes well to an arbitrary number of dimensions. DOK is well-suited for writing and mutating. Most other operations are not supported for DOK. A common workflow may involve writing an array with DOK and then converting to another format for other operations.
The Compressed Sparse Row/Column (CSR/CSC) formats are widely used in scientific computing are now supported by pydata/sparse. The CSR/CSC formats excel at compression and mathematical operations. While these formats are restricted to two dimensions, pydata/sparse supports the GCXS sparse array format, based on GCRS/GCCS from which generalizes CSR/CSC to n-dimensional arrays. Like their two-dimensional CSR/CSC counterparts, GCXS arrays compress well. Whereas the storage cost of COO depends heavily on the number of dimensions of the array, the number of dimensions only minimally affects the storage cost of GCXS arrays, which results in favorable compression ratios across many use cases.
Together these formats cover a wide array of applications of sparsity.
Additionally, with each format complying with the numpy.ndarray interface and
following the appropriate dispatching protocols,
pydata/sparse arrays can interact with other array libraries and seamlessly
take part in pydata-ecosystem-based workflows.
LICENSE
This library is licensed under BSD-3