Hi, this is a draft of a post, but it could be already useful.
Dense Matrix Multiplication Example
The simplest the most common formats used.
CSR Sparse Matrix Multiplication Example
A very common sparse format that is useful in situations described in below.
Sparse Matrix Formats
Sparse matrix format compresses matrices with more than half zero values and speeds up certain operations on them. There are two main groups of the sparce matrix representations:
- efficient for incremental construction and modification DOK, LIL, COO
- efficient for access and operations CSR, CSC
There are several types of sparse matrix representations, where each has an advantage in different situations.
- DOK: Dictionary of Keys format:
- row, column pairs map to value,
dict((i, j): matrix[i, j] for i in matrix.shape for j in matrix.shape)
- LOL: List of Lists format:
- each row has one list of tuples of column and value
[[(j, matrix[i,j]) for j in range(matrix.shape)] for i in range(matrix.shape)]
- COO: COOrdinate format (aka IJV, triplet format):
- sorted list of row, column, value tuples
[(i, j, matrix[i, j]) for i in range(matrix.shape) for j in range(matrix.shape)]
- CSC: Compressed Sparse Row format: COO
- stores matrix in 3 lists
- “row list” for each row contains a number that is references a position in the value and column lists, where the row’s column and values start
- “column list” contains column indexes and is indexed by the row list
- “value list” contains values and is indexed by the row list
- to access a row
indexes = range(row_list[i], row_list[i+1]), then build row’s list of list representation
row_lol = [(i, column_list[j], value_list[j]) for j in indexes]
- fast matrix to vector multiplication (product) thus useful for KNN
- fast CSR + CSR, CSR * CSR, CSR * Dense
- row slicing
- converting to Scipy’s CSR with
- and more: Compressed Sparse Row, Block Sparse Row format, Diagonal, …