Stored zeros in SparseMatrixCSC

[ViralBShah]

There is a need to allow stored zeros in SparseMatrixCSC. We just need to check which routines may be affected, and what the implications of this could be.

[mlubin]

Which routines besides nnz need to be modified?

Repeating from the previous discussion, the idea is that stored zeros are convenient for some applications, so they should be allowed. The only extra overhead of having stored zeros should be the cost of the extra operations.

[ViralBShah]

We'll have to figure out if the sparse solvers are ok with stored zeros. If not, we'll have to add a squeeze zeros operation every time. Nothing else comes to mind immediately.

[lindahua]

Allowing stored zeros are of course useful -- we have a lot of applications where the sparse pattern is fixed and elements there may sometimes become zero (e.g. in an iterative graph-based algorithm, the set of edges are fixed, but the weights attached to some edges may temporarily set to zeros).

Here, we may need two functions: nnz to return the actual number of non-zero and another function to the number of explicitly stored values.

[mlubin]

The overwhelming majority of the time when dealing with sparse matrices, one will want the number of explicitly stored values. The number of actual non-zeros is more of a side case, maybe the function nnz should have a longer name?

[ViralBShah]

I would like to keep the implementation free of stored zeros - so sparse etc. will continue to squeeze out the zeros, and routines such as binary operations will continue to check that they do not store zeros. We could have a flag called hasStoredZeros, which is set by users who need the feature. The sparse runtime can then respect this flag in all operations.

[mlubin]

I don't see why any extra metadata is needed. Base functions should continue to pack down zeros when it's appropriate, the only guarantee that should be provided is that the functions work correctly when the input has explicit zeros.

[ViralBShah]

That would be ideal. Let's implement this on a branch and take it from there.

[lindahua]

what about a keyword argument removezeros (or whatever) which by default set to true?

This is usable when working with both graphs & sparse matrices. Sometimes I don't want edges be implicitly removed from the representation simply because their weights are zeros.

This option would not break any existing code (since the default behavior remains as original), and will not introduce a lot of complication (as it only affects a little bit of the constructor). No additional field is needed.

[JeffBezanson]

How can you tell whether an edge is removed from a sparse matrix, or set to zero? Won't you get the same results either way? Is the only difference performance?

[lindahua]

One only sees the difference when he works with the internal representation. My argument was kind of speculative at this point. I thought about it more, it doesn't seem like matter a lot. So I am fine with either way.