wiki 稀疏矩陣: 稀疏矩陣（sparse matrix），在數值分析中，是其元素大部分為零的矩陣。反之，如果大部分元素都非零，則這個矩陣是稠密 (dense matrix) 的。在科學與工程領域中求解線性模型時經常出現大型的稀疏矩陣。在使用電腦儲存和操作稀疏矩陣時，經常需要修改標準演算法以利用矩陣的稀疏結構。由於其自身的稀疏特性，通過壓縮可以大大節省稀疏矩陣的記憶體代價。更為重要的是，由於過大的尺寸，標準的演算法經常無法操作這些稀疏矩陣。

矩陣的主要有兩種表示法：稠密矩陣 (Dense Matrix) 以及稀疏矩陣 (Sparse Matrix)

舉例來說圖片中的矩陣

如果將所有資料依序存下，那這個就會是以 Dense Matrix 來表示
這邊又會分成 row major 或 column major 的兩種形式

row major = 
  [ 3 0 0 0 2 1 0 0 0 0 0 1 4 0 0 2]
column major =
  [ 3 2 0 4 0 1 0 0 0 0 0 0 0 0 1 2]

可以看到兩者差別在於儲存資料的順序不一樣

另外儲存資料時會有另一個參數 stride 或者 leading number (ld)，這個值代表當程式要怎麼找下一列的起始點

row major = 
  [ 3 0 0 0 X, 2 1 0 0 X, 0 0 0 1 X, 4 0 0 2 X]
column major =
  [ 3 2 0 4 X, 0 1 0 0 X, 0 0 0 0 X, 0 0 1 2 X]

例如：row_major 當第 1 列使用完後會用第 1 列起始點配合 stride 來找第 2 列的起始點，row_major 第二列的起始點 = row_major 第一列的起始點 + stride = 5 + 5 = 10。那如果看到 lda 或 ldb 就是指 leading number of A 或 leading number of B 分別給不同的矩陣使用。

稀疏矩陣 (Sparse Matrix)

像前面那個例子矩陣有很多零，那是不是可以只存非零元素 (nonzero) 來節省空間稀疏矩陣有更多種儲存資料的方式，不同類型的可以適用在不同的問題上面，常見的有 Compressed sparse row (CSR) (也有人使用 CRS - Compressed row storage) Coordinate (COO) 以及 Ellpack (ELL)

CSR

CSR 會有三個陣列分別儲存 - 值 (value)、行座標 (column index)、列指標 (row pointer) (這邊的中文是我大致上猜的，如果有更合適不容易混淆的方式，在下面留言跟我說)

• value - 會儲存前面提到的非零元素 (nonzero)
• column index - 儲存相對應的行座標 (column)
• row pointer - 紀錄每一列的起頭位置

因此上面例子可以記錄成以下

val = [ 3 2 1 1 4 2 ]
col_idx = [ 0 0 1 3 0 3 ]
row_ptr = [ 0 1 3 4 6 ] 

row pointer 會多一個在最末端來告知最後一列結束的位置，所以也可以拿來當作整個矩陣有的非零元素個數 (the number of nonzeros, nnz)

row_ptr(i) row_ptr(i+1) 可以表示第 i 列的頭跟尾，例如我們想要知道第一列有哪些元素，row_ptr(2)= 1,row_ptr(3) = 3 表示 val, col_idx 的 1 ~ 2 (3是屬於下一列的) 是屬於第一列的 A(1, *) ，再對照裡面的值我們可以得知 A(1, 0) = 2, A(1, 1) = 1

那假設在使用雙精準浮點數 (double - 8 byte) 以及整數 (int - 4 byte) 來儲存的話是否會帶來差別呢

• Dense: 8 * 16 = 128 byte
• CSR: 8 * 6 [val] + 4 * 6 [col_idx] + 4 * (4 + 1) [row_ptr] = 48 + 24 + 20 = 92 byte

可以看到 CSR 在這個例子的確可以用比較少的儲存空間來表示這個矩陣

COO

COO 十分直接，把每一個元素都存下她的值以及座標，所以會有 value, col_idx, row_idx

val     = [ 3 2 1 1 4 2 ]
col_idx = [ 0 0 1 3 0 3 ]
row_idx = [ 0 1 1 2 3 3 ]

也可以看到有 6 個非零元素，所以每一個陣列也都會是 6 個

雖然理論上 COO 不用管順序，但在實務上她的排序方式會要求 row major 也就是 row_idx 會為遞增數列

這裡也算一下她使用的空間： (8 + 4 + 4) * 6 = 96

ELL

ELL 將 row 這個資訊也隱藏在陣列的儲存裏頭，不像 COO 或 CSR 會有一個陣列指出哪一塊是第幾列。將 DENSE 多紀錄一個行 (col) 的資訊，然後把多餘的零刪掉

val 每一列就是對應到原先矩陣的那一列，然後相對應的位置 col_idx 會記錄行座標，那這邊 val 的寬度就會是原先矩陣最多非零元素那一列的數量。因此，如果某一列都是非零，就會導致 val 的大小跟原先一樣，反而要多花空間去紀錄 col_idx

另外注意的是，通常 ELL 會以 col_major 來處理，所以實際上記憶體上來看會長這樣

val     = [ 3 2 1 4 * 1 * 2 ]
col_idx = [ 0 0 3 0 * 1 * 3 ]

* 的部分就要看實作時的用法，那通常會是放 -1 或者 0
這裡的空間所需 : (8 + 4) * (4 * 2) = 96 byte

總結

當一個矩陣零占多數時，可以考慮用稀疏矩陣來做處理。CSR 以及 COO 是比較常見的類型，像是 cuSPARSE 11 之後就只剩下 CSR、COO 以及 BSR (未介紹)，而 intel oneMKL 目前也只有 CSR，hipSPARSE 目前應該還是跟著 cuSPARSE 10.2 的，所以還是有 CSR, COO, ELL, HYBRID 等。那 ELL 好處在於當你每一列的元素數量都差不多的時候，是一個好平行且高效的格式；但如果某一列有太多元素，可能會比 DENSE 的方式還不好。