Sparse Matrix Format

Sparse Matrix

filter3D plot from SuiteSparse Collection

Point Cloud from open3D document

Sparse matrix requires lot more consideration than when dealing with dense data, especially on GPUs. A sparse matrix is a matrix in which most of the elements are zero. It is important to understand the sparse matrix because a lot of data, for example, social network representing relationships between nodes or point clouds storing 3D-points information are sparse.

 

Matrix Representation

There are several format to represent the matrix, but here will introduce 3 type of data formats.

• Dense array
• COO(Coordinate list) / Triplet
• CSR/CSC(Compress Sparse Row/Column)

 

Dense array format is efficient in that it is intuitive and allows direct memory access. But when the matrix is sparse, there are only a few meaningful nnz(number non-zero elements), the space complexity is too high. If the data is 2- dimension, the space complexity is \(O(n^2)\), if 3-dimension \(O(n^3)\).

 

# coo_list(row, column, value)
coo_list = [[0,0,10],[0,1,20],[1,1,30],[1,3,40],[2,2,50],[2,3,60],[2,4,70],[5,5,80]]

COO or Triplet format stores a list of (row, column, value) types. Ideally, the entries are sorted by index to improve random access time. The advantage of using the coo format is that it stores only non-zero elements, so it's space complexity is \(O(E)\), where E is the nnz in the matrix. However, the COO format has fatal disadvantages in that there is no locality of data and direct memory acess is impossible. For example, it is inefficient when performing operations where the position of an element is important, such as convolution of matrix multiplication.

 

# CSR format
row_ptr = [0, 2, 4, 7, 8]			
col_idx = [0, 1, 1, 3, 2, 3, 4, 5]
val = [10, 20, 30, 40, 50, 60, 70, 80]

Compressed Sparse Row format represents a matrix M by three arrays(row pointer, column index, value), that respectively contain non-zero values. The only difference to COO format is that row_ptr stores the address of the first non-zero elements of each row. The space complexity of Compressed Sparse Format is \(O(E+V)\) where V is number of rows or columns. The CSC and CSR formats are similar to COO, but they are often used in sparse matrix multiplication because some efficient memory access is possible using row pointer arrays.

 

Irregular distribution