【Advanced Chapter】Sparse Matrix Techniques: Storage Optimization and Computation Methods in MATLAB

# 2.1 Sparse Matrix Storage Formats

Sparse matrix storage formats are designed to efficiently store and access non-zero elements, ***mon storage formats include:

- **Compressed Row Storage (CSR)**: Rows of the sparse matrix are stored in a compressed manner, represented by three arrays: row index array (rows), column index array (cols), and value array (vals). Here, rows store the starting position of each row, cols store the column indices of the non-zero elements in each row, and vals store the values of the non-zero elements.

- **Compressed Column Storage (CSC)**: Similar to CSR, CSC stores the sparse matrix by column. It consists of three arrays: column index array (cols), row index array (rows), and value array (vals). Here, cols store the starting position of each column, rows store the row indices of the non-zero elements in each column, and vals store the values of the non-zero elements.

- **Hash Table Storage**: Sparse matrices are stored using a hash table, where the key is the element's coordinates and the value is the element's value. This format allows for rapid access to individual elements, but the storage overhead can be significant for large sparse matrices.

# 2. Sparse Matrix Storage Optimization

## 2.1 Sparse Matrix Storage Formats

Sparse matrix storage formats are intended to efficiently represent sparse matrices, minimizing storage space and computational time. The most commonly used formats include:

### 2.1.1 Compressed Row Storage (CSR)

The CSR format stores a sparse matrix as three arrays:

- Row pointer array: Stores the starting positions of each row.
- Column index array: Stores the column indices of each non-zero element.
- Value array: Stores the values of each non-zero element.

# Creating a sparse matrix in CSR format
import numpy as np
from scipy.sparse import csr_matrix

data = np.array([1, 2, 3, 4, 5])
rows = np.array([0, 0, 1, 1, 2])
cols = np.array([0, 2, 0, 1, 0])
A = csr_matrix((data, (rows, cols)), shape=(3, 3))

# Printing the CSR formatted sparse matrix
print(A)

**Parameter Explanation:**

- `data`: A one-dimensional array of non-zero element values.
- `rows`: A one-dimensional array of row indices for non-zero elements.
- `cols`: A one-dimensional array of column indices for non-zero elements.
- `shape`: The shape of the sparse matrix.

**Code Logic Analysis:**

The CSR format stores a sparse matrix as three arrays, each storing specific information. The `data` array stores the values of the non-zero elements, the `rows` array stores the row indices of the non-zero elements, and the `cols` array stores the column indices of the non-zero elements. Using the row pointer array, non-zero elements for each row can be quickly accessed.

### 2.1.2 Compressed Column Storage (CSC)

The CSC format is similar to CSR but stores the sparse matrix as three arrays:

- Column pointer array: Stores the starting positions of each column.
- Row index array: Stores the row indices of each non-zero element.
- Value array: Stores the values of each non-zero element.

**Code Example:**

# Creating a sparse matrix in CSC format
from scipy.sparse import csc_matrix

data = np.array([1, 2, 3, 4, 5])
rows = np.array([0, 0, 1, 1, 2])
cols = np.array([0, 2, 0, 1, 0])
A = csc_matrix((data, (rows, cols)), shape=(3, 3))

# Printing the CSC formatted sparse matrix
print(A)

**Parameter Explanation:**

- `data`: A one-dimensional array of non-zero element values.
- `rows`: A one-dimensional array of row indices for non-zero elements.
- `cols`: A one-dimensional array of column indices for non-zero elements.
- `shape`: The shape of the sparse matrix.

**Code Logic Analysis:**

The CSC format stores a sparse matrix as three arrays, each storing specific information. The `data` array stores the values of the non-zero elements, the `rows` array stores the row indices of the non-zero elements, and the `cols` array stores the column indices of the non-zero elements. Using the column pointer array, non-zero elements for each column can be quickly accessed.

### 2.1.3 Hash Table Storage

The hash table storage format stores a sparse matrix as a hash table, where the key is a tuple `(row, col)` and the value is the value of the non-zero element. This format is suitable for sparse matrices with highly irregular distributions of non-zero elements.

**Code Example:**

# Creating a sparse matrix in hash table format
from collections import defaultdict

A = defaultdict(lambda: 0)
A[(0, 0)] = 1
A[(0, 2)] = 2
A[(1, 0)] = 3
A[(1, 1)] = 4
A[(2, 0)] = 5

# Accessing a non-zero element
print(A[(0, 0)])

**Parameter Explanation:**

- `A`: A sparse matrix in hash table format.
- `(row, col)`: The row index and column index of the non-zero element.

**Code Logic Analysis:**

The hash table storage format stores a sparse matrix as a hash table, where the key is a tuple `(row, col)` and the value is the value of the non-zero element. Using a hash table, non-zero elements can be quickly accessed, even if the distribution of non-zero elements is highly irregular.

### 2.2 Storage Optimization Algorithms

#### 2.2.1 Sequential Sorting

Sequential sorting algorit