search

josdejong / mathjs

An extensive math library for JavaScript and Node.js
https://mathjs.org
Apache License 2.0
14.41k stars 1.24k forks source link

Sparse Matrix implementation #335

Closed rjbaucells closed 9 years ago

rjbaucells commented 9 years ago

I opened this issue to start a conversation about the implementation I worked on related to Sparse Matrices. I implemented two Sparse Matrix storage formats, the Compressed Column Storage CCS and the Compressed Row Storage CRS. The two storage formats are very similar, in fact they are the same one looked from a row index (CRS) and the other from a column index (CCS).

At the beginning I though we needed both storage formats since one has advantages over the other for some cases; as an example, if an algorithm needs to process a row at a time the CRS is the way to go if it needs to process a column at a time the CCS is better.

Having both formats is putting an overhead on the algorithm implementations since we have to implement all possible combinations. For example a simple Matrix * Matrix multiplication will need 9 different implementations since we have three formats available (dense, ccs and crs). See current v2 implementation of multiply().

The majority of algorithms I have seen are designed for CCS, it is the format used by Matlab, Scilab and others. So what I am proposing here is to drop CRS (in V2) and implement everything related to sparse matrices using CCS.

We will leave the pluggable architecture in place so more storage formats can be added if needed for a specific algorithm. This way we can check at the beginning if the storage format is compatible with the algorithm and throw an exception if this is not the case.

What do you think?

josdejong commented 9 years ago

Thanks for opening this discussion. It makes sense to me to just keep one of the two sparse matrix implementations, that will make things a lot easier, and I think you are right that we would not loose that much functionality.

I'm ok with removing CRS and just keeping CCS. How do you think about renaming CcsMatrix to SparseMatrix, and change creation from math.matrix([...], 'ccs') to math.matrix([...], 'sparse')? We could also introduce a new convenience function math.sparse([...]) like Matlab has. That may make things more intuitive to use.

rjbaucells commented 9 years ago

Perfect, we will move on that direction...