possible support for sparse arrays

[dcherian]

@ilan-gold @ivirshup if you have time, it'd be nice to see a groupby-reduce workflow you'd like to see supported natively by flox.

[ivirshup]

Thanks for opening the issue!

I think the workflows we'd like to see are pretty straight forward. We'd like:

• the array being computed on to be sparse (e.g. the first argument), but producing a dense result
• The distributed array being computed on to have sparse chunks
• Probably some additional reduction methods that ignore zeros. At the very least a count_nonzero/ nzcount (btw, would love suggestions on naming here) method

I've thought a little bit about implementation.

• I don't know if a ufunc based approach will work. I recall @seberg working on some ufunc methods for sparse arrays at a sprint, but don't recall if it ended up working out
• I think only the in-memory array computing layer would need any work, as combining stats across chunks should be the same
• I haven't figured out how this fits in with the existing engines. Aside from just implementing sparse support in numpy_groupies
• A graphblas engine would probably be very fast here
• I only really care about 2d sparse arrays at the moment

[seberg]

I recall @seberg working on some ufunc methods for sparse arrays at a sprint, but don't recall if it ended up working out

That mostly worked, but was a bit slow. The point being that the approach was to extract the result sparsity pattern. Then extract the data and apply the normal ufunc to it. But at least for memory bound ufuncs like add, it was much slower (maybe 3-4x, but don't recall). Now, of course that could probably be optimized a bit by specialization e.g. of binary ufuncs. But in the end, the way scipy-sparse works, it seemed potentially useful as a fallback to implement any ufunc for any dtype NumPy supports, even if scipy sparse has never heard of them. But probably not as a replacement for most operations.

[dcherian]

@ivirshup is there an existing algorithm for grouping a sparse array, by a dense array, producing a dense array? Is there a preferred format here? GCXS seems like a much better fit than COO, for example.