---
title: Sparse Matrix Abstract Data Type
sticky: false
tags:
- Data Structure
categories: [Data Structure]
comments: true
date:
---
# Sparse Matrix Abstract Data Type
## 1. 什麼是稀疏矩陣 (Sparse Matrix)?
一個矩陣中，大部分元素為零，只有少部分是非零元素，就稱為稀疏矩陣。
以下是一個 $6 \times 6$ 的矩陣，只有 **8/36** 的元素不為零：
$$
\left[
\begin{array}{cccccc}
15 & 0 & 0 & 22 & 0 & -15 \\
0 & 11 & 3 & 0 & 0 & 0 \\
0 & 0 & 0 & -6 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
91 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 28& 0 & 0 & 0 \\
\end{array}
\right]
$$
## 2. 為什麼需要 Sparse Matrix ADT?
前情提要：
### 二維陣列表示法
在數學中，一個矩陣包含 $m$ 行與 $n$ 列的元素，通常寫成 $m \times n$（讀作 "m by n"）。
矩陣的總元素數量是 $mn$。(若 $m = n$，則此矩陣稱為 **方陣 (square matrix)**。)
在 computer science 中，矩陣的**標準表示法**是一個二維陣列，例如：
`a[MAX_ROWS][MAX_COLS]`
### 標準表示法的問題
然而，若矩陣中存在大量 **零元素**，上述表示法就會造成 **記憶體浪費**。
舉例來說：
- 在上一個 $6 \times 6$ 的矩陣中，只有 8 個元素不為零，卻要存下 36 個位置。
- 更極端的例子是 $1000 \times 1000$ 矩陣（共 $1,000,000$ 個元素），若大部分元素為 0，則浪費空間非常嚴重。
此外，**運算效率** 也會下降：
- 矩陣加法或乘法會進行大量「$0 + 0$」或「$0 \times 0$」的無效運算。
因此，我們應該用其他方法來表示稀疏矩陣。
## 3. 稀疏矩陣的表示
表示稀疏矩陣最常見的方法之一是 **三元組 (3-Tuple) 表示法**。
### 三元組 (3-Tuple) 表示法
在這種表示法中，每個非零元素都以一個三元組 `<row, col, value>` 來記錄：
- `row`：該元素的列索引
- `col`：該元素的行索引
- `value`：該元素的值
這樣，我們就不用存下所有的 $0$，只需要記錄非零值與它的位置即可。
舉例來說，剛剛的 $6 \times 6$ 矩陣可以被轉換成下列表格：
| a[i] | row | col | value |
|------|-----|-----|-------|
| a[0] | 6 | 6 | 8 |
| a[1] | 0 | 0 | 15 |
| a[2] | 0 | 3 | 22 |
| a[3] | 0 | 5 | -15 |
| a[4] | 1 | 1 | 11 |
| a[5] | 1 | 2 | 3 |
| a[6] | 2 | 3 | -6 |
| a[7] | 4 | 0 | 91 |
| a[8] | 5 | 2 | 28 |
:::warning
在實作時，通常會把第一筆資料 `a[0]` 用來存放矩陣的基本資訊：
- 總列數 (rows)
- 總行數 (cols)
- 非零元素數量 (nonzeros)
其餘的 `a[1] ~ a[k]` 則存放真正的三元組資料。
:::
:::info
為了讓後續對矩陣的操作更有效率，我們要求：
- 三元組按照 **row 升序** 排列
- 同一 row 內再按照 **col 升序** 排列
:::
## 4. 稀疏矩陣的操作 (Operations)
稀疏矩陣 (Sparse-Matrix) ADT 主要有四種基本操作：
### Create (max-row, max-col)
建立一個稀疏矩陣，並記錄其大小與非零元素。
### Transpose (a)
將矩陣轉置，把每個元素的 row 與 col 對調。
### Add (a, b)
若兩個矩陣的大小相同，則可進行加法，將對應位置的元素相加。
### Multiply (a, b)
若 `a` 的欄數等於 `b` 的列數，則可進行矩陣乘法，產生新的稀疏矩陣。
:::info
這四種操作構成了 Sparse-Matrix ADT 的核心功能，後續我們會再說明它們的實作方式。
:::
## 5. 矩陣 Create
### Create (max-row, max-col) 的功能
建立一個稀疏矩陣，並能記錄：
- 矩陣的總列數 (rows)
- 矩陣的總行數 (cols)
- 非零元素的數量 (nonzeros)
- 各個非零元素的三元組 <row, col, value>
### 實作範例
C
```c
#define MAX_TERMS 101 // 最多能存放的三元組數量 (+1 儲存矩陣資訊)
typedef struct {
int row; // 列索引
int col; // 行索引
int value; // 非零元素的值
} term;
term a[MAX_TERMS]; // 用來存放稀疏矩陣
```
C++
```C++
const int MAX_TERMS = 101; // 最多能存放的三元組數量 (+1 儲存矩陣資訊)
struct Term {
int row; // 列索引
int col; // 行索引
int value; // 非零元素的值
};
Term a[MAX_TERMS]; // 用來存放稀疏矩陣
```
#### 二維轉一維的概念
在一般情況下，矩陣是一個 **二維結構**，必須用 `a[i][j]` 來存取元素。
但在稀疏矩陣中，大多數元素為零，沒必要全部存下，所以我們將它「壓縮」成一個 **一維陣列**：
- **a[0]**：用來存放矩陣的基本資訊
- `row` → 總列數
- `col` → 總行數
- `value` → 非零元素數量
- **a[1] ~ a[k]**：存放真正的非零元素 `<row, col, value>`
這樣就相當於把原本的 **二維矩陣**，轉換成一個 **一維的三元組陣列**：
- 節省了空間
- 提升了矩陣操作的效率
## 6. 矩陣轉置 (Transpose)
### 1. 定義
**轉置 (Transpose)**：將矩陣的 **行 (row)** 和 **列 (col)** 交換。
- 原矩陣的元素：`a[i][j]` → 轉置後變成 `b[j][i]`。
- 在三元組表示法下，就是把 `<row, col, value>` → 轉置後變成`<col, row, value>`。
### 2. 直觀想法
演算法流程：
```text
for each row i
take element <i, j, value> and store it
as <j, i, value> of the transpose;
```
::: warning
如果我們單純按照 **row 的順序** 來處理轉置，會遇到一個問題：
無法立即確定 `<i, j, value>` 在轉置矩陣中的正確位置，往往要等到之前所有元素都處理完後才能決定。
例如：
(0, 0, 15) → (0, 0, 15)
(0, 3, 22) → (3, 0, 22)
(0, 5, -15) → (5, 0, -15)
(1, 1, 11) → (1, 1, 11)
前三個元素轉置後看似符合順序，但當 `(1, 1, 11)` 放進去時，才發現它應該排在 `(0, 0, 15)` 之後。
這代表在插入新元素時，必須重新掃描、調整順序，甚至將後續元素整體往下移動，導致效率非常低。
:::
### 3. 一般轉置 (Transpose)
演算法流程：
```text
for all elements in column j
place element <i, j, value> in
element <j, i, value>
```
換句話說，這個演算法的核心概念是：
- 先找到原矩陣 **第 0 欄 (column 0)** 的所有元素，把它們依序放到轉置矩陣的 **第 0 列 (row 0)**。
- 接著處理 **第 1 欄 (column 1)**，把元素放到轉置後的 **第 1 列 (row 1)**。
- 依此類推，直到所有欄位處理完畢。
因為原本的三元組矩陣是依照 **row（列）優先，再按照 col（行）遞增** 來存放的。
所以：
- 在原矩陣裡，元素是照 **列數由小到大** 排列，同一列再按照 **行數由小到大**。
- 轉置後，會變成照 **行數由小到大** 排列，同一行再按照 **列數由小到大**。
因此不需要額外重排。
#### 實作範例
```c
void transpose(term a[], term b[])
/* b is set to the transpose of a */
{
int n, i, j, currentb;
n = a[0].value; /* 非零元素的總數 */
b[0].row = a[0].col; /* b 的總列數 = a 的總行數 */
b[0].col = a[0].row; /* b 的總行數 = a 的總列數 */
b[0].value = n; /* 非零元素個數一樣 */
if (n > 0) { /* 如果不是零矩陣 */
currentb = 1; /* b 的第一個非零元素位置 */
/* 外層：依照 a 的 column 來掃描 */
for (i = 0; i < a[0].col; i++) {
/* 內層：檢查所有非零元素 */
for (j = 1; j <= n; j++) {
if (a[j].col == i) { /* 找到屬於當前欄 i 的元素 */
/* 將它轉置後存入 b */
b[currentb].row = a[j].col;
b[currentb].col = a[j].row;
b[currentb].value = a[j].value;
currentb++;
}
}
}
}
}
```
:::info
註：變數 `currentb`用來記錄轉置矩陣 b 中下一個要存放的位置。
:::
#### 時間複雜度分析
對轉置演算法的時間分析其實很簡單，因為決定計算時間的關鍵是 **巢狀 for 迴圈**。
其他語句（例如 `if` 判斷與幾個指派語句）只需要常數時間，可以忽略不計。
- 外層 `for` 迴圈：會執行 `a[0].col` 次，其中 `a[0].col` 是原始矩陣的 **欄數 (columns)**。
- 內層 `for` 迴圈：每次迭代需要掃描 `a[0].value` 個元素，其中 `a[0].value` 是矩陣中的 **非零元素數量 (elements)**。
因此，巢狀迴圈的總時間大約是：
$T \approx \text{columns} \times \text{elements}$
所以，這個演算法的漸近時間複雜度為：
$O(\text{columns} \times \text{elements})$
這樣的時間稍微令人困擾，因為如果矩陣是用 **二維陣列 (rows × columns)** 來表示，只需要：
$O(\text{rows} \times \text{columns})$ 的時間就能完成轉置。
實現方式很簡單：
```c
for (i = 0; i < rows; i++)
for (j = 0; j < cols; j++)
b[j][i] = a[i][j];
```
換句話說，為了節省空間（使用三元組表示法），我們付出了額外的時間成本。
那麼，有沒有辦法 在壓縮空間的同時，讓轉置速度更快 呢？
### 4. 快速轉置 (Fast Transpose)
:::success
目標：把一般轉置的時間從 $O(\text{columns} \times \text{elements})$ 降到 $O(\text{columns} + \text{elements})$
:::
做法（核心三步）：
1. **統計每欄數量**：掃描原矩陣 `a`，計算每個欄位的非零元素數量 → `row_terms[col]`。
2. **計算起始位置**：依 `row_terms` 做前綴和，得到轉置矩陣 `b` 中每一列（=原矩陣的每一欄）的**起始寫入位置** → `starting_pos[row]`。
3. **直接放到正確位置**：再掃一遍 `a`，把 `<r,c,val>` 轉成 `<c,r,val>`，寫入 `b[starting_pos[c]]`，並將 `starting_pos[c]++`。
> 直觀理解：先知道「每一列會放幾個、從哪裡開始放」，就能一次把元素丟到對的位置，完全避免搬移與重排。
---
#### 實作範例
```c
#define MAX_COL 50 /* 最大欄數 + 1，依需求調整 */
typedef struct {
int row, col, value;
} term;
/* 將 a 的轉置放入 b（a, b 皆為三元組陣列；a[0] 與 b[0] 存基本資訊） */
void fast_transpose(term a[], term b[]) {
int row_terms[MAX_COL], starting_pos[MAX_COL];
int i, j;
int num_cols = a[0].col; /* 原矩陣的欄數 = 轉置後的列數 */
int num_terms = a[0].value; /* 非零元素數量 */
/* b 的基本資訊 */
b[0].row = num_cols; /* b 的列數 = a 的欄數 */
b[0].col = a[0].row; /* b 的欄數 = a 的列數 */
b[0].value = num_terms;
if (num_terms > 0) {
/* Step 1: 統計每欄的非零數量 */
for (i = 0; i < num_cols; ++i) row_terms[i] = 0;
for (i = 1; i <= num_terms; ++i) row_terms[a[i].col]++;
/* Step 2: 計算每列的起始位置（前綴和） */
starting_pos[0] = 1; /* 三元組資料從 b[1] 開始寫入 */
for (i = 1; i < num_cols; ++i)
starting_pos[i] = starting_pos[i-1] + row_terms[i-1];
/* Step 3: 按正確位置寫入轉置結果 */
for (i = 1; i <= num_terms; ++i) {
j = starting_pos[a[i].col]++; /* 取得該列的下一個可用位置 */
b[j].row = a[i].col; /* 轉置後的 row = 原本的 col */
b[j].col = a[i].row; /* 轉置後的 col = 原本的 row */
b[j].value = a[i].value;
}
}
}
```
::: info
在轉置矩陣中，要計算 **第 $i$ 列 $(i > 1)$** 的起始位置：
$\text{starting_pos}[i] = \text{row_terms}[i-1] + \text{starting_pos}[i-1]$
其中：
- `row_terms[i-1]` = 轉置矩陣第 $i-1$ 列中的元素個數。
- `starting_pos[i-1]` = 第 $i-1$ 列的起始位置。
這樣我們就能保證每一列的起點與元素數量正確，進而確保元素被放到正確位置。
:::
#### 時間複雜度分析
快速轉置演算法的時間主要來自四個迴圈：
1. **第一個迴圈**：初始化 `row_terms`，次數 = `num_cols`。
2. **第二個迴圈**：計算每一欄的元素數量，次數 = `num_terms`。
3. **第三個迴圈**：計算每列的起始位置 `starting_pos`，次數 = `num_cols - 1`。
4. **第四個迴圈**：將三元組搬到轉置矩陣的正確位置，次數 = `num_terms`。
由於每個迴圈內部的操作只需要常數時間，所以總時間為：
$O(\text{columns} + \text{elements})$
### 5. 演算法比較
一般的 Transpose 演算法需要的時間是 $O(\text{columns} \times \text{elements})$
因為外層要跑過所有欄數，內層則必須掃描所有非零元素。當非零元素數量很多時，這種方法的效率會變得很差。
Fast Transpose 的時間則能降到 $O(\text{columns} + \text{elements})$
它透過先計算每一欄的非零元素數量，再決定轉置矩陣中每一列的起始位置，最後把元素一次放到正確位置，避免了不必要的重複掃描。這使得在稀疏矩陣中，它的效率特別突出。
至於二維陣列轉置，如果我們直接用完整的 rows × columns 陣列來存矩陣，那麼轉置僅需要 $O(\text{rows} \times \text{columns})$
因為每個元素（不論是否為零）都能直接搬到正確位置。這種方法對於非稀疏矩陣來說很合適，但在稀疏矩陣中就浪費了大量運算。
## 7. 矩陣乘法 (Matrix Multiplication)
### 1. 定義
假設有兩個矩陣：
- $A$：大小 $m \times n$
- $B$：大小 $n \times p$
則它們的乘積 $D = A \times B$ 為一個大小 $m \times p$ 的矩陣， 其元素定義為：
$d_{ij} = \sum_{k=0}^{n-1} a_{ik} \cdot b_{kj},\quad 0 \leq i < m, \; 0 \leq j < p$
### 2. 實作
#### 基本想法
計算方式如下：
- 選取矩陣 $A$ 的一列 $i$。
- 對於每個 $j = 0, 1, \dots, \text{cols}_B - 1$，尋找矩陣 $B$ 的第 $j$ 欄的所有元素。
- 將 $A$ 的第 $i$ 列與 $B$ 的第 $j$ 欄做內積，得到 $D_{ij}$。
#### 問題
如果單純依序尋找 $B$ 的每一欄，我們必須 **掃描整個 $B$**，才能找到指定欄位的所有元素，這樣效率非常差。
---
#### 改進方法
先計算 $B$ 的轉置矩陣 $B^T$。
這樣一來：
- $B$ 的「第 $j$ 欄」元素，在 $B^T$ 中就會變成「第 $j$ 列」。
- 這能保證同一欄的元素在記憶體中是 **連續存放** 的。
:::info
#### 為什麼要掃完整個 $B$ 才能找到欄 $j$？
以三元組序列表示的稀疏矩陣，資料是依 **列優先、同列內再依欄遞增** 排序並存放的。也就是說，記憶體中的三元組會先按 $row$ 分成一段一段的區間，每一段內再按 $col$ 排序。當我們想要「取出欄 $j$ 的所有非零元素」時，這些元素其實散落在不同的 $row$ 區間之中，並不連續。因此，在未轉置的情況下，想收集欄 $j$ 的元素，就只能把 $B$ 的所有三元組都檢查一遍，篩出 $col = j$ 的那些元素。
#### 為什麼先轉置 $B$ 就能變快？
將 $B$ 轉成 $B^{\mathsf T}$ 後，原本的「欄 $j$」就變成 $B^{\mathsf T}$ 的「列 $j$」。而三元組是 **列優先** 儲存的，於是列 $j$ 的所有三元組在 $B^{\mathsf T}$ 中恰好形成一段連續區間。
:::
#### 程式碼範例
$mmult$
```c
void mmult(term a[], term b[], term d[])
/* multiply two sparse matrices */
{
int i, j, column, totalb = b[0].value, totald = 0;
int rows_a = a[0].row, cols_a = a[0].col,
totala = a[0].value;
int cols_b = b[0].col,
row_begin = 1, row = a[1].row, sum = 0;
int new_b[MAX_TERMS][3];
if (cols_a != b[0].row) {
fprintf(stderr,"Incompatible matrices\n");
exit(1);
}
fast_transpose(b,new_b);
/* set boundary condition */
a[totala+1].row = rows_a;
new_b[totalb+1].row = cols_b;
new_b[totalb+1].col = 0;
for (i = 1; i <= totala;) {
column = new_b[1].row;
for (j = 1; j <= totalb+1;) {
/* multiply row of a by column of b */
if (a[i].row != row) {
storesum(d,&totald,row,column,&sum);
i = row_begin;
for (; new_b[j].row == column; j++);
column = new_b[j].row;
}
else if (new_b[j].row != column) {
storesum(d,&totald,row,column,&sum);
i = row_begin;
column = new_b[j].row;
}
else switch (COMPARE(a[i].col, new_b[j].col)) {
case -1: /* go to next term in a */
i++; break;
case 0: /* add terms, go to next term in a and b */
sum += (a[i++].value * new_b[j++].value);
break;
case 1: /* advance to next term in b */
j++; break;
}
}
for (; a[i].row == row; i++);
row_begin = i; row = a[i].row;
}
d[0].row = rows_a;
d[0].col = cols_b;
d[0].value = totald;
}
```
$storesum$
```c
void storesum(term d[], int *totald, int row, int column, int *sum)
{
/* if *sum != 0, then it along with its row and column
position is stored as the *totald+1 entry in d */
if (*sum)
if (*totald < MAX_TERMS) {
d[++*totald].row = row;
d[*totald].col = column;
d[*totald].value = *sum;
*sum = 0;
}
else {
fprintf(stderr,"Numbers of terms in product exceeds %d\n",MAX_TERMS);
exit(1);
}
}
```
接下來我們來解析一下這個程式
**各變數的角色**
`a[]`：矩陣 $A$ 的三元組，依 $row$ 優先，再 $col$ 升序排列。
`b[]`：矩陣 $B$ 的三元組。
`new_b[]`：矩陣 $B$ 的轉置（即 $B^T$），這樣「$B$ 的欄」會變成「`new_b` 的列」，方便掃描。
`d[]`：結果矩陣 $D$ 的三元組 ( $D = A \times B$ )。
`row`：目前正在處理的 $A$ 的列。
`row_begin`：$A$ 中該列的第一個元素在陣列 `a` 的起始位置。
`column`：目前正在與 $A$ 的某列相乘的 $B$ 的欄（實作上對應 `new_b` 的某一列）。
`i`：掃描 $A$ 的當前列中的元素。
`j`：掃描 `new_b` 的當前列（即 $B$ 的某一欄）。
`sum`：累加器，用來計算當前結果元素 $D \ [row, column]$。
`totala` = `a[0].value`：$A$ 的非零元素數量。
`totalb` = `b[0].value`：$B$ 的非零元素數量。
---
**核心想法**
矩陣乘法定義：
$D\ [row,column] = \sum_{k} A\ [row,k] \cdot B\ [k,column]$
所以我們需要「合併兩個有序串列」：
一邊是 $A\ [row, *]$ 的所有 $k$ 值。
一邊是 $B\ [*, column]$ 的所有 $k$ 值 。
當兩邊的 $k$ 相等時 → 相乘後累加到 `sum`。
否則 → 移動較小的一邊。
這就是 `COMPARE(a[i].col, new_b[j].col)` 的邏輯。
----
**函式解釋**
#### `storesum` 在做什麼?
**1. 檢查 sum 是否非零**
`*sum` 代表「當前正在計算的某一個結果位置 (row, column) 的累加值」。
如果 `*sum == 0`，就代表這個位置沒有結果（完全是零），不用存。
**2. 把結果存進矩陣 d**
`++*totald` 會把總元素數量加一，並把這個新元素存到 `d[*totald]`。
同時記錄它的 `row`、`col`、`value`。
**3. 把 sum 歸零**
因為這個位置的結果已經存起來了，`sum` 要重設成 0，方便下一次累加新的位置。
**4. 錯誤檢查**
如果結果超過 `MAX_TERMS`，表示結果矩陣裝不下，就輸出錯誤並退出。
---
#### 為什麼需要 `storesum`？
在矩陣相乘過程中，我們其實是「逐行 × 逐欄」去做：
對 $A$ 的第 $i$ 列和 $B$ 的第 $j$ 欄進行比對，會產生一個 $\text{sum} = \sum_k a_{ik} b_{kj}$
這個 sum 算完以後，就應該存到結果矩陣 $D$ 的位置 $(i, j)$。
`storesum` 就是專門做這件事的函式。
---
#### `mmult` 在做什麼？
`mmult` 是用來計算兩個稀疏矩陣相乘的函式，輸入矩陣為 `a` 和 `b`，輸出結果放到 `d`。
**1. 初始化與檢查**
- 先取出矩陣 $A$ 和 $B$ 的維度（列數、欄數、非零元素數量）。
- 檢查是否符合矩陣相乘的條件：$A$ 的欄數要等於 $B$ 的列數。
- 如果不符合，直接輸出錯誤訊息並結束程式。
**2. $B$ 轉置處理**
- 呼叫 `fast_transpose(b, new_b)` 把矩陣 $B$ 轉置，得到 `new_b`。
- 為什麼要轉置？
因為矩陣相乘時需要頻繁存取 $B$ 的「欄」，轉置後就能用 **列的方式連續存取**，效率更高。
**3. 設定邊界條件 (sentinels)**
- 在 `a` 和 `new_b` 的最後各加上一個「$dummy \ term$ 」。
- 這能避免在迴圈中不斷檢查「是否到尾端」，讓程式更簡潔。
**4. 外層迴圈：掃描 $A$ 的每一列**
- 使用 `row_begin` 和 `row` 記錄目前在 $A$ 的哪一列。
- 每次固定 $A$ 的一列，接著和 $B$ 的所有欄逐一相乘。
**5. 內層迴圈：合併列 $×$ 欄**
- 設定 `column = new_b[1].row`，也就是 B 的第一欄。
- 掃描 $A$ 的一列與 $B$ 的一欄，把對應元素做比較 (`COMPARE`)：
- **$case -1$**：$A$ 的欄索引 < $B$ 的欄索引 → 移動到 $A$ 的下一個元素。
- **$case 0$**：索引相同 → 把兩元素相乘並累加到 `sum`。
- **$case 1$**：$B$ 的欄索引比較小 → 移動到 $B$ 的下一個元素。
:::spoiler 內層邏輯詳細說明
1. 初始化 `column`
```c
column = new_b[1].row;
```
→ 從 $B$ 的第一欄開始（在 `new_b` 裡就是第 $1$ 列）。
2. 掃描 `new_b`
```c
for (j = 1; j <= totalb + 1;)
```
→ 依序走過 `new_b` 的所有元素。
3. 檢查是否換 $A$ 的列
```c
if (a[i].row != row) {
storesum(d,&totald,row,column,&sum);
i = row_begin;
for (; new_b[j].row == column; j++);
column = new_b[j].row;
}
```
→ 如果已經超過目前這一列，就把 `sum` 存起來，然後回到這一列的開頭，準備處理下一個 `column`。
4. 檢查是否換 $B$ 的欄
```c
else if (new_b[j].row != column) {
storesum(d,&totald,row,column,&sum);
i = row_begin;
column = new_b[j].row;
}
```
→ 當 `j` 移動到 $B$ 的下一個欄時，先把這一列$×$上一欄的結果存好，再從頭開始處理這一列和新的欄。
5. 比較 $A$ 和 $B$ 的索引
```c
else switch (COMPARE(a[i].col, new_b[j].col)) {
case -1: i++; break;
case 0: sum += a[i++].value * new_b[j++].value; break;
case 1: j++; break;
}
```
→ 執行「合併操作」，對齊同樣的 $k$，才能計算內積。
:::
**6. 存結果**
- 當一個 $(row, column)$ 的內積計算完成時，呼叫 `storesum` 把 `sum` 存入結果矩陣 `d`，然後把 `sum` 歸零。
**7. 更新迴圈狀態**
- 用 `row_begin` 記錄下一列的起始位置，準備處理 $A$ 的下一列。
- 最後，更新 `d[0]` 的 `row`、`col`、`value`，表示乘積矩陣 $D$ 的維度與總非零元素數量。
:::info
#### 什麼是 $dummy\ terms$？
在 `mmult` 的實作中，我們會在矩陣 $A$ 和 $B$ 的三元組陣列最後，各加上一個「假的元素 ($dummy \ term$)」，這些元素不屬於矩陣本身，只是用來輔助演算法判斷邊界。
#### 為什麼需要 $dummy\ terms$？
當我們在迴圈裡處理三元組時，需要知道「目前是否已經到達最後一列或最後一欄」。
如果沒有 $dummy\ terms$，就必須額外檢查「是否越界」，讓程式碼變得複雜。
加入 $dummy\ terms$ 後，演算法就可以在迴圈中自動結束。
**在程式中的使用**
```c
a[totala+1].row = rows_a; // A 的 dummy term
new_b[totalb+1].row = cols_b; // B 的 dummy term
new_b[totalb+1].col = 0;
```
`a[totala+1].row = rows_a`
→ 標記 $A$ 已經處理到最後一列。
`new_b[totalb+1].row = cols_b, new_b[totalb+1].col = 0`
→ 標記 $B$ 的轉置矩陣已經處理到最後一欄。
:::
#### 時間複雜度分析
#### **前置步驟（轉置 $B$ 矩陣**）
`fast_transpose(b, new_b)` 的時間複雜度是
$$
O(\text{cols}_b + \text{total}_b)
$$
---
#### 單次外層迭代（固定 A 的某一列）
外層迴圈的名義上限是 `totala`，但實際執行過程要更仔細拆開來看：
- 在處理 A 的某一列時，`i` 會依序前進，最多掃過該列的 $\text{terms_row}$ 個非零元素。
- 由於這一列必須和 B 的**所有 $\text{cols}_b$ 欄**相乘，每當切換到下一欄，就需要把 `i` 重設為 `row_begin`，重新從頭比對。
因此，對一列來說，重設的次數上界就是 $O(\text{cols}_b)$。
- 同時，`j` 在整體過程中會遍歷 B 的所有非零元素，因此最多前進 $\text{total}_b + 1$ 次。
綜合來看，掃描一列的成本來自兩部分：
1. `i` 的掃描與重設，對於 A 的這一列，會有 $\text{terms_row}$ 個非零元素需要逐一處理。
而且因為這一列要和 **所有 $\text{cols}_b$ 個欄**相乘，每次跨欄都要重新回到該列的開頭來做比對。
因此，對這一列來說，額外的開銷就是 $O(\text{cols}_b \cdot \text{terms_row})$。 。
2. `j` 的遍歷，在固定 A 的某一列時，這一列的所有元素都必須與 B 的每一欄相乘。
由於 B 的每一欄中可能包含非零項，我們必須逐一檢查，因此需要 **跑過 B 的所有非零項**。
換句話說，就是要掃過 $\text{total}_b$ 個元素。
合併起來，單次迭代的時間成本為：
$$
O(\text{cols}_b \cdot \text{terms_row} + \text{total}_b)
$$
---
#### 全部外層迭代（掃完 A 的所有列）
把上式對所有列加總（所有列的非零數量總和為 $\text{total}_a$，列數為 $\text{rows}_a$），得到：
$$
\sum_{\text{rows}} O(\text{cols}_b \cdot \text{terms_row} + \text{total}_b)
= O(\text{cols}_b \cdot \underbrace{\sum \text{terms_row}}_{=\ \text{total}_a}) \;+\; O(\underbrace{\sum 1}_{=\ \text{rows}_a} \cdot \text{total}_b)
$$
化簡後為：
$$
O(\text{cols}_b \cdot \text{total}_a + \text{rows}_a \cdot \text{total}_b)
$$
---
#### 合併前置成本
再把一開始轉置 $b$ 的成本 $O(\text{cols}_b + \text{total}_b)$ 合併進來，整體時間複雜度為：
$$
O(\text{cols}_b + \text{total}_b) \;+\; O(\text{cols}_b \cdot \text{total}_a + \text{rows}_a \cdot \text{total}_b)
= O(\text{cols}_b \cdot \text{total}_a + \text{rows}_a \cdot \text{total}_b)
$$
Sign in with Wallet
Connect another wallet