Clever Geek Handbook

How to store a sparse matrix?

I need to implement 2 types of sparse matrix storage in C ++:

  • Linked list
  • Array (efficient way)

The complexity of the space is very important here. What are the most efficient ways to do this?

+3


source to share


3 answers


nnz

: non-zero number of sparse matrix
row_size

: row number of matrix
column_size

: column number of matrix
There are many ways, their spatial complexity:

  • Compressed Sparse Series (CSR): 2*nnz + row_size

    amount of memory
  • Compressed Sparse Column (CSC): 2*nnz + column_size

    amount of memory
  • Coordinate format (COO): 3*nnz

    amount of memory

For space complexity:
If row_size > column_size

, use format CSC

, otherwise use format CSR

.



For time complexity:
For format, the CSR

row will be indexed by O(1)

time, the column will be indexed by time O(log(k))

, binary search for the column, k

is the number of non-zero element of this row. Thus, the value will be time-indexed O(log(k))

.
For format, the COO

value will be indexed in O(1)

time.

Format information
[1] https://en.wikipedia.org/wiki/Sparse_matrix
[2] https://software.intel.com/en-us/node/471374

+2


source


Since the matrix is ​​sparse, you only need to keep the filled cells. You need to do a simple coordinate lookup for the value. Ideally, you should use something with fast lookup like O (log n) map or unordered_map O (1).



0


source


An efficient way would be to use a hashmap (per row) of hashmaps (to store the items in each row by column index). Then there will be access to any element in O (1) time.

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

0


source






More articles:


All Articles