TW Community

稀疏矩陣 (Sparse Matrix) 介紹

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

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

舉例來說圖片中的矩陣

matrix

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

row major or 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)

另外儲存資料時會有另一個參數 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 - 紀錄每一列的起頭位置
csr 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) 的資訊,然後把多餘的零刪掉

ell

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 的方式還不好。

想要問一下有特別在哪個時候會用到ELL的嗎?因為在這些方法中,感覺ELL看起來好像比較不穩定

這就要看處理的問題了,例如 PDE 等會有矩陣去描述每個點跟旁邊怎麼互動,如果比較一般的可能就會是 5 (2d) 或者 7 (3d) 等這種形式出現,每一列的個數就會大多一樣。
的確 ELL 相對起來適用條件比較嚴格一點,但也有一些去利用 ELL 的益處的格式,如 SELLP 或 Hybrid 等。
如果沒有要從矩陣格式開始做的話,並考量到一些函式庫的情況, CSR 還是比較通用的選擇,或者 COO。這些都是要根據所要處理的問題去決定的。