I am trying to select the best scipy sparse matrix type to use in my algorithm. In that, I should initialize data in a vij way, then I should use it to perform matrix vector multiplication. Eventually I have to add rows and cols. Trying to select the best for my problem, I want to understand which are the best cases to use each of this types: lil_matrix, coo_matrix, csr_matrix, csc_matrix, dok_matrix. Can someone explain me? Its not necessary to show examples of all the types in the same answer.
2 Answers
Ok, I was looking for an answer and now I have it clearer: Scipy documentation does not elaborate too much on the explanation, but wikipedia article is much more clear. For those who are looking for an answer, there are two major groups of sparse matrices:
a) Sparse types used to construct the matrices:
DOK (Dictionary Of Keys): a dictionary that maps (row, column) to the value of the elements. It uses a hash table so it's efficient to set elements.
LIL (LIst of Lists): LIL stores one list per row. The lil_matrix format is row-based, so if we want to use it then in other operations, conversion to CSR is efficient, whereas conversion to CSC is less so.
COO (COOrdinate list): stores a list of (row, column, value) tuples.
b) Sparse types that support efficient access, arithmetic operations, column or row slicing, and matrix-vector products:
CSR (Compressed Sparse Row): similar to COO, but compresses the row indices. Holds all the nonzero entries of M in left-to-right top-to-bottom ("row-major") order (all elements in the first row, all elements in the second row, and so). More efficient in row indexing and row slicing, because elements in the same row are stored contiguously in the memory.
CSC (Compressed Sparse Column): similar to CSR except that values are read first by column. More efficient in a column indexing and column slicing.
Once the matrices are build using one of the a) types, to perform manipulations such as multiplication or inversion, we should convert the matrix to either CSC or CSR format.
If you wish an easy to understand implementation that has the opportunity to make the matrix bigger as well as being able to row/column operation, I suggest you coo_matrix. coo_matrix is efficient and fast to construct but, arithmetic operations are not efficient on this matrix. Instead, you can easily convert coo_matrix to csc_matrix/csr_matrix that are efficient in column_slicing/row_slicing so you can have efficient multiplication or inversion.