Sparse Matrix Why and When?

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[0] for j in matrix.shape[1])

LOL: List of Lists format:

• each row has one list of tuples of column and value
• example [[(j, matrix[i,j]) for j in range(matrix.shape[1])] for i in range(matrix.shape[0])]

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[0]) for j in range(matrix.shape[1])]

CSR: Compressed Sparse Row format

• 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 i retrieve 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
• fast row slicing
• slow transpose
• converting to Scipy’s CSR with tocsr method

CSC: Compressed Sparse Column format

• similar to CSR except columns and rows switch their role

Other formats

Block Sparse Row format, Diagonal, …

How to Use Sparse Matrices

You can use Scipy library for sparce matrixes. The main image is from this study.