---
# System prepended metadata

title: Sparse Matrix Abstract Data Type
tags: [Data Structure]

---

---
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)
$$  

 