Python multi dimensional sparse array

Question

I am working on a project where I need to deal with 3 dimensional large array. I was using numpy 3d array but most of my entries are going to be zero, so it's lots of wastage of memory. Scipy sparse seems to allow only 2D matrix. Is there any other way I can store 3D sparse array?

Answer 1

scipy.sparse has a number of formats, though only a couple have an efficient set of numeric operations. Unfortunately, those are the harder ones to extend.

dok uses a tuple of the indices as dictionary keys. So that would be easy to generalize from 2d to 3d or more. coo has row, col, data attribute arrays. Conceptually then, adding a third depth(?) is easy. lil probably would require lists within lists, which could get messy.

But csr and csc store the array in indices, indptr and data arrays. This format was worked out years ago by mathematicians working with linear algebra problems, along with efficient math operations (esp matrix multiplication). (The relevant paper is cited in the source code).

So representing 3d sparse arrays is not a problem, but implementing efficient vector operations could require some fundamental mathematical research.

Do you really need the 3d layout to do the vector operations? Could you, for example, reshape 2 of the dimensions into 1, at least temporarily?

Element by element operations (*,+,-) work just as well with the data of a flattened array as with the 2 or 3d version. np.tensordot handles nD matrix multiplication by reshaping the inputs into 2D arrays, and applying np.dot. Even when np.einsum is used on 3d arrays, the product summation is normally over just one pair of dimensions (e.g. 'ijk,jl->ikl')

3D representation can be conceptually convenient, but I can't think of a mathematical operation that requires it (instead of 2 or 1d).

Overall I think you'll get more speed from reshaping your arrays than from trying to find/implement genuine 3d sparse operations.

Answer 2

You're right; it doesn't look like there are established tools for working with n-dimensional sparse arrays. If you just need to access elements from the array there are options using a dictionary keyed on tuples. See:

sparse 3d matrix/array in Python?

If you need to do operations on the sparse 3d matrix, it gets harder- you may have to do some of the coding yourself.

Answer 3

See the python library: https://sparse.pydata.org/en/stable/construct.html

An example in 2D is given below - copied from the page provided above. However, it also works for more than 2 dimensions. I am currently working with a variable number of dimensions using this library. Just as a small note: in case of a sparse matrix with more than 2 dimensions, a conversion to the known SciPy sparse matrices is not possible.

import sparse

coords = [[0, 1, 2, 3, 4],

          [0, 1, 2, 3, 4]]

data = [10, 20, 30, 40, 50]

s = sparse.COO(coords, data, shape=(5, 5))

s.todense()
array([[10,  0,  0,  0,  0],
       [ 0, 20,  0,  0,  0],
       [ 0,  0, 30,  0,  0],
       [ 0,  0,  0, 40,  0],
       [ 0,  0,  0,  0, 50]])

Answer 4

take a look at github/sparse or pytorch-documentation/sparse. see code snippet (pytorch one) below.

import numpy as np
import torch

N0,N1,N2 = 3,4,5
np_rng = np.random.default_rng()
np0 = np_rng.normal(size=(N0,N1,N2)) * (np_rng.uniform(size=(N0,N1,N2))>0.8) #some fake 3d data

index = np.stack(np.nonzero(np0)) #(np,int64,(3,nnz))
value = np0[index[0], index[1], index[2]] #(np,float64,nnz)

torch0_coo = torch.sparse_coo_tensor(index, value, (N0,N1,N2))
torch0_coo.shape #(3,4,5)
torch0_coo.dtype #float64
torch0_coo.indices() #(torch,int64,(ndim,nnz))
torch0_coo.values() #(torch,float64,nnz)