SciPy CSR vs CSC: Sparse Matrix Storage Differences

This article provides a comparison of the Compressed Sparse Row (CSR) and Compressed Sparse Column (CSC) matrix storage formats in Python's SciPy library. While both formats drastically reduce memory consumption by storing only non-zero elements, their internal structures prioritize different memory layouts. Below, we break down how each format organizes data internally, the structural differences in their index pointer arrays, and how their memory arrangements impact operational efficiency.

The Three-Array System

Both scipy.sparse.csr_matrix and scipy.sparse.csc_matrix store sparse data using three one-dimensional NumPy arrays:

1. data: Contains the actual non-zero values of the matrix.
2. indices: Contains the coordinate indices for each element in data.
3. indptr: Contains pointers indicating where each row or column starts and ends within data and indices.

The key difference between CSR and CSC is how these three arrays represent rows versus columns.

Compressed Sparse Row (CSR) Storage

CSR organizes data along rows (row-major order). It traverses the matrix left-to-right, top-to-bottom.

• data: Stores non-zero values traversed row-by-row.
• indices: Stores the column index for each corresponding entry in data. Length is equal to the number of non-zero elements (\(NNZ\)).
• indptr: Represents row boundaries. The elements at row i are found in data[indptr[i]:indptr[i+1]], with corresponding column positions in indices[indptr[i]:indptr[i+1]]. The length of indptr is n_rows + 1.

CSR Example

For the following \(3 \times 3\) matrix:

[[1, 0, 2],
 [0, 0, 3],
 [4, 5, 0]]

The CSR arrays are:

• data: [1, 2, 3, 4, 5]
• indices (column positions): [0, 2, 2, 0, 1]
• indptr (row offsets): [0, 2, 3, 5]

Compressed Sparse Column (CSC) Storage

CSC organizes data along columns (column-major order). It traverses the matrix top-to-bottom, left-to-right.

• data: Stores non-zero values traversed column-by-column.
• indices: Stores the row index for each corresponding entry in data. Length is equal to \(NNZ\).
• indptr: Represents column boundaries. The elements at column j are found in data[indptr[j]:indptr[j+1]], with corresponding row positions in indices[indptr[j]:indptr[j+1]]. The length of indptr is n_cols + 1.

CSC Example

For the same \(3 \times 3\) matrix:

[[1, 0, 2],
 [0, 0, 3],
 [4, 5, 0]]

The CSC arrays are:

• data: [1, 4, 5, 2, 3]
• indices (row positions): [0, 2, 2, 0, 1]
• indptr (column offsets): [0, 2, 3, 5]

Key Storage and Performance Trade-Offs

1. Memory Footprint Variation

The total memory of both formats is primarily determined by \(2 \times NNZ\) (for data and indices). However, the size of indptr varies:

• CSR indptr size: n_rows + 1
• CSC indptr size: n_cols + 1

For non-square matrices, CSR is slightly more memory-efficient when n_rows < n_cols, while CSC is more memory-efficient when n_cols < n_rows.

2. Slicing and Access Patterns

• CSR: Fast row slicing (matrix[i, :]) because all elements of a given row are contiguous in memory. Column slicing (matrix[:, j]) is slow because it requires scanning through the entire indices array.
• CSC: Fast column slicing (matrix[:, j]) because column entries are contiguous in memory. Row slicing (matrix[i, :]) is slow for the same reason.

3. Arithmetic Operations

• CSR is optimized for matrix-vector multiplication (\(Ax\)) and operations involving row-wise iterations.
• CSC is optimized for column-wise operations, solving linear systems where column pre-ordering is applied, and transposed matrix-vector multiplication (\(A^T x\)).