Sparse Matrices

Dense Matrices

A $n\times n$ matrix is called dense if it has $O(n^2)$ non-zero entries. For example:

To store the matrix, all components are saved in row-major order. For $\mathbf{A}$ given above, we would store:

The dimensions of the matrix are stored separately.

Sparse Matrices

A $n\times n$ matrix is called sparse if it has $O(n)$ non-zero entries. For example:

COO (Coordinate Format) stores arrays of row indices, column indices and the corresponding non-zero data values in any order. This format provides fast methods to construct sparse matrices and convert to different sparse formats. For $\mathbf{A}$ the COO format is:

CSR (Compressed Sparse Row) encodes rows offsets, column indices and the corresponding non-zero data values. This format provides fast arithmetic operations between sparse matrices, and fast matrix vector product. The row offsets are defined by the followign recursive relationship (starting with $\text{rowptr}[0]=0$):

where $\mathrm{nnz}({\text{row}}_k)$ is the number of non-zero elements in the $k^{th}$ row. Note that the length of $\text{rowptr}$ is $n_{rows}+1$, where the last element in $\text{rowptr}$ is the number of nonzeros in $A$. For $\mathbf{A}$ the CSR format is:

CSR Matrix Vector Product Algorithm

The following code snippet performs CSR matrix vector product for square matrices:

import numpy as np
def csr_mat_vec(A, x):
  Ax = np.zeros_like(x)
  for i in range(x.shape[0]):
    for k in range(A.rowptr[i], A.rowptr[i+1]):
      Ax[i] += A.data[k]*x[A.col[k]]
  return Ax

Review Questions

• See this review link

  ChangeLog

• 2020-03-01 Peter Sentz: extracted material from previous reference pages