Support for sparse matrices

[zkbpkp]

I need sparse matrices (CSR, CSC) support. Does nalgebra provide it? If no, are there plans to support it?

[sebcrozet]

No, nalgebra does not implement sparse matrices. We don't plan to implement them ourselves in the near-future, but any contribution is welcome!

The current traits that abstract the matrix data storage (Storage, StorageMut, etc.) assume that the components are stored contiguously or with regular strides. So sparse matrices won't be able to implement them. Thus, I think there are two options:

1. Change those traits to make them even more abstract (e.g. by requiring only methods that return iterators on the matrix components instead of direct pointers to the underlying buffer). This might degrade the performance of existing implementations of dense matrix operations (because the optimizer would be disturbed by the iterators).
2. Don't change any trait, and implement sparce matrix as a different type than Matrix. This is the route taken by, e.g., Eigen. I think this second option is both easier to implement and will allow better optimizations (especially because template specialization is not stable yet in Rust).

[sebcrozet]

Note that I have started some work on sparse matrices in the sparse branch. It isn't complete nor polished yet but it is a start we can improve in the future. So far I focused on:

• CSC storage.
• Sparse matrix/sparse matrix product.
• Sparse matrix/dense matrix product.
• Lower-triangular system resolution.
• Cholesky decomposition (both left-looking and up-looking. We still need a supernodal implementation).

[ralfbiedert]

Just to follow up #498, from ffsvm's perspective (sorry, not familiar with matrix storage lingo):

• Ability to dynamically construct sparse vectors at runtime
• Set elements in random order (not hard requirement, just convenience)
• Get next non-zero (index, value) pair very efficiently, with ordered index traversal
• Get value for random index at "reasonable" speed

[ChristopherRabotin]

Has there been any development on sparse matrix implementation since the comment above? And if not, what library is recommended for sparse matrices? Thanks

[sebcrozet]

@ChristopherRabotin No, there haven't been much development on sparse matrices lately. All the supported features are on the sparse module.

what library is recommended for sparse matrices?

The only alternative I am aware of is https://crates.io/crates/sprs. Not sure how complete it is.

[Andlon]

Has there been any development on sparse matrix implementation since the comment above? And if not, what library is recommended for sparse matrices? Thanks

See also #592. In particular, I have quite a bit of the design discussed there implemented, but I can not pack it up for contribution before February at the earliest.

[Andlon]

There is now nalgebra-sparse, which provides CSR, CSC and COO matrices.

While it doesn't explicitly support sparse vectors, it's possible to use a Nx1 CSC matrix for this purpose.