Hypersparse matrix class proposal
Submitted by Dmitry Zhdanov
Assigned to Dmitry Zhdanov
Link to original bugzilla bug (#1179)
Version: 3.4 (development)
Description
I implemented a class for hypersparce (NxM) matrices such that nnz<<max(N,M), where nnz is number of nonzero elements. This class allows to dramatically reduce the storage requirements (O(nnz) instead of O(min(N,M))) and affords an opportunity to essentially speed up basic matrix operations with such matrices.
Technically, the class is based on doubly compressed sparse column\row (DCSC(R)) data structure (see e.g. A. Buluc¸ and J. R. Gilbert "On the representation and multiplication of hypersparse matrices", in IPDPS’08: Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing, IEEE Computer Society, Washington, DC, 2008, pp. 1–11).
My implementation seems to be compatible with the Eigen 3.3 and is based on step-by-step reproduction of SparseMatrix.h functionality (except for diagonal traits which I did not test). So, by their construction, the DCSC(R) matrices are well integrated into Eigen and can be used virtually everywhere instead of ordinary Eigen sparse matrices. However, the computational performance is not optimal (i.e. it is similar to one for usual sparse matrices) because of some generic limitations of generic Eigen sparse iterators. To avoid these limitations wrote some ad-hoc utilities which might be interesting on their own (for example, parallel vectorized algorithm for (hyper)sparse-(hyper)sparse matrix multiplication which resembles one used in Matlab). I am actively using DCSC class in my quantum chemistry research where it is really indispensable.
So, there are 3 questions to Eigen developers.
- Would you be interested to see the hypersparse matrices as a part of Eigen project?
- If so, would you be willing to add some features to generic SparseMatrix implementation to allow for the performance improvements for DCSC(R) matrices?
- Are you interested in including implementations of high-performance (hyper)sparse-(hyper)sparse matrix multiplications?