Menu
I need to implement 2 types of storing sparse matrix in C++:
Space complexity is very important here. What are the most effective ways to do it?
468
To store the sparse vector efficiently, a vector of pairs can be used. The First element of pair will be the index of sparse vector element(which is non-zero) and the second element will be the actual element.
However, if a matrix has most of its elements equal to zero, then the matrix is known as a sparse matrix. In the case of a sparse matrix, we don't store the zeros in the memory to reduce memory usage and make it more efficient. We only store the non-zero values of the sparse matrix inside the memory.
Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in the matrix are of no use in most of the cases. So, instead of storing zeroes with non-zero elements, we only store non-zero elements. This means storing non-zero elements with triples- (Row, Column, value).
In the computer memory, all elements are stored linearly using contiguous addresses. Therefore, in order to store a two-dimensional matrix a, two dimensional address space must be mapped to one-dimensional address space. In the computer's memory matrices are stored in either Row-major order or Column-major order form.
nnz : non-zero number of sparse matrixrow_size : matrix row numbercolumn_size : matrix column number
There are many ways, their space complexity :
2*nnz + row_size number of memory 2*nnz + column_size number of memory 3*nnz number of memoryFor space complexity :
If row_size > column_size, use CSC format, otherwise, use CSR format.
For Time complexity:
For CSR format, Row will be indexed by O(1) time, Column will be indexed by O(log(k)) time, by binary search the Column, k is the number of non-zero element of that row. So value will be indexed by O(log(k)) time.
For COO format, value will be indexed in O(1) time.
Format details
[1] https://en.wikipedia.org/wiki/Sparse_matrix
[2] https://software.intel.com/en-us/node/471374
143
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
