CSR Sparse Matrix Multiplication

Introduction

The compressed sparse row (CSR) format is used for encoding sparse matrix. Depending on the level of sparsity, the memory consumption and the computation cost of some of the matrix operations could be significantly reduced.

There are existing software which accelerates sparse matrix operations, such as cuSPARSE and SciPy. But high-level users usually don’t care how sparse matrix operations were implemented.

In this blog post, I would like to quickly discuss the CSR matrix and how CSR matrix multiplication is performed.

CSR Matrix

Suppose we have a (row-major) matrix $\mathbf{M} \in \mathbb{R}^{m \times n}$ in which there are $k$ non-zero values.

To represent the matrix using dense matrix format, we will need the following information.

• The value array $\mathbf{v} \in \mathbb{R}^{mn}$.
• The matrix shape $(m, n)$.

To represent the matrix using sparse CSR matrix format, we will need the following information.

• The value array $\mathbf{v} \in \mathbb{R}^{k}$.
• The column index array $\mathbf{c} \in \mathbb{R}^{k}$. This is also sometimes called the index array.
• The row index array $\mathbf{r} \in \mathbb{R}^{m + 1}$. This is also sometimes called the pointer array. The first element in $\mathbf{r}$, $\mathbf{r}[0]$, always equal to 0. The last element in $\mathbf{r}$, $\mathbf{r}[m]$, always equal to $k$. The number of non-zero values in row $i$ is $\mathbf{r}[i + 1] - \mathbf{r}[i]$.
• The matrix shape $(m, n)$.

For example, suppose we have the following matrix $\mathbf{M} \in \mathbb{R}^{5 \times 7}$,

\begin{align} \mathbf{M} &= \begin{bmatrix} 10 & 20 & 0 & 0 & 0 & 0 & 0 \\ 0 & 30 & 0 & 40 & 0 & 0 & 0 \\ 0 & 0 & 50 & 60 & 70 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 80 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix} \end{align}

The corresponding CSR matrix representation should be

\begin{align} \mathbf{v} &= \begin{bmatrix} 10 & 20 & 30 & 40 & 50 & 60 & 70 & 80 \\ \end{bmatrix} \\ \mathbf{c} &= \begin{bmatrix} 0 & 1 & 1 & 3 & 2 & 3 & 4 & 5 \\ \end{bmatrix} \\ \mathbf{r} &= \begin{bmatrix} 0 & 2 & 4 & 7 & 8 & 8 \\ \end{bmatrix} \\ \end{align}

To save memory, the number of non-zero values $k$ must be

$$k < \frac{mn -m - 1}{2}$$

Advantages of the CSR format

• Efficient arithmetic operations CSR + CSR, CSR $\times$ CSR, etc.
• Efficient row slicing.
• Fast matrix vector products.

Disadvantages of the CSR format

• Slow column slicing operations.
• Changes to the sparsity structure are expensive.

CSR Matrix Multiplication

Because it is inefficient to slice along the the column for CSR matrix, one of the matrix multipliers was transposed before multiplication. The transpose takes $O(N \log N)$ operations where $N$ is the number of non-zero elements in the matrix. The multiplication takes an additional $O(MN)$ operations where $M$ and $N$ are the numbers of non-zero elements in the two multiplier matrices. So if $M \gg \log N$, we could say the asymptotic complexity for CSR matrix multiplication is $O(MN)$.

Python Implementation

The Python implementation is used for demonstrating how to compute CSR matrix multiplication algorithmically. While the implementation is definitely not efficient because it is in Python and has never been optimized, the algorithm complexity should be asymptotically optimal.

Lei Mao

12-21-2022

12-21-2022