CODEWITHSUNDEEP
c++time-complexitysparse-matrix
sayhello
sayhello

Reputation: 185

How to store sparse matrix?

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?

Upvotes: 6

Views: 8435

Answers (3)

pgplus1628
pgplus1628

Reputation: 1374

nnz : non-zero number of sparse matrix
row_size : matrix row number
column_size : matrix column number
There are many ways, their space complexity :

  • Compressed Sparse Row (CSR) : 2*nnz + row_size number of memory
  • Compressed Sparse Column (CSC) : 2*nnz + column_size number of memory
  • Coordinate Format (COO) : 3*nnz number of memory

For 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

Upvotes: 4

Ivan Mushketyk
Ivan Mushketyk

Reputation: 8285

An efficient way would be to use hash map (for each row) of hash maps (to store elements in each row by column index). Then would be able to access any element in O(1) time.

You can implement all numeric algorithms, like addition and multiplication iterating only through non-zero elements which will give you better complexity then O(N * M) where N and M are number of columns and rows in a matrix.

Upvotes: 2

doron
doron

Reputation: 28882

Since the matrix is sparse, you only need to store the cells that are filled in. A simple lookup of coordinate to value should do. Ideally you should use something with fast lookup like a map O(log n) or a unordered_map O(1).

Upvotes: 1

Related Questions