稀疏矩陣理論與實踐

1.稀疏矩陣的優化
? 多線程。使用openmp或者mpi
? numanode awareness 特性。把稀疏矩陣的存儲均勻地分配到兩顆處理器各自的本地內存中，最大程度的利用內存帶寬
? 利用硬件cache特性，對矩陣進行分塊或矩陣的循環進行限制
? 利用pipeline，多流水線并行處理
? 自適應分塊存儲結構。由于稀疏矩陣的非零元分布不一定均勻，有的分塊會非常稀疏，有的則會相對稠密。對于極稀疏的分塊（非零元數量遠小于行數），如果用和CSR相似的壓縮行存儲策略，則會浪費空間，所以用COO的方式反而更能節省存儲空間，提高訪問效率。

2. 矩陣（稀疏矩陣）壓縮存儲（3種方式）
   數據結構中，提供針對某些特殊矩陣的壓縮存儲結構。
   這里所說的特殊矩陣，主要分為以下兩類：
   ? 含有大量相同數據元素的矩陣，比如對稱矩陣；
   ? 含有大量 0 元素的矩陣，比如稀疏矩陣、上（下）三角矩陣；
   針對以上兩類矩陣，數據結構的壓縮存儲思想是：矩陣中的相同數據元素（包括元素 0）只存儲一個。
   對稱矩陣
   

圖 1 對稱矩陣示意圖
圖 1 的矩陣中，數據元素沿主對角線對應相等，這類矩陣稱為對稱矩陣。

矩陣中有兩條對角線，其中圖 1 中的對角線稱為主對角線，另一條從左下角到右上角的對角線為副對角線。對稱矩陣指的是各數據元素沿主對角線對稱的矩陣。
結合數據結構壓縮存儲的思想，可以使用一維數組存儲對稱矩陣。由于矩陣中沿對角線兩側的數據相等，因此數組中只需存儲對角線一側（包含對角線）的數據即可。
對稱矩陣的實現過程是，若存儲下三角中的元素，只需將各元素所在的行標 i 和列標 j 代入下面的公式：

存儲上三角的元素要將各元素的行標 i 和列標 j 代入另一個公式：

最終求得的 k 值即為該元素存儲到數組中的位置（矩陣中元素的行標和列標都從 1 開始）。
例如，在數組 skr[6] 中存儲圖 1 中的對稱矩陣，則矩陣的壓縮存儲狀態如圖 3 所示（存儲上三角和下三角的結果相同）：

圖 3 對稱矩陣的壓縮存儲示意圖
注意，以上兩個公式既是用來存儲矩陣中元素的，也用來從數組中提取矩陣相應位置的元素。例如，如果想從圖 3 中的數組提取矩陣中位于 (3,1) 處的元素，由于該元素位于下三角，需用下三角公式獲取元素在數組中的位置，即：

結合圖 3，數組下標為 3 的位置存儲的是元素 3，與圖 1 對應。

上（下）三角矩陣

圖 4 上(下)三角矩陣

如圖 4 所示，主對角線下的數據元素全部相同的矩陣為上三角矩陣（圖 4a)），主對角線上元素全部相同的矩陣為下三角矩陣（圖 4b)）。

對于這類特殊的矩陣，壓縮存儲的方式是：上（下）三角矩陣采用對稱矩陣的方式存儲上（下）三角的數據（元素 0 不用存儲）。

例如，壓縮存儲圖 4a) 中的上三角矩陣，矩陣最終的存儲狀態同圖 3 相同。因此可以得出這樣一個結論，上(下)三角矩陣存儲元素和提取元素的過程和對稱矩陣相同。
稀疏矩陣

圖 5 稀疏矩陣示意圖

如圖 5 所示，如果矩陣中分布有大量的元素 0，即非 0 元素非常少，這類矩陣稱為稀疏矩陣。

壓縮存儲稀疏矩陣的方法是：只存儲矩陣中的非 0 元素，與前面的存儲方法不同，稀疏矩陣非 0 元素的存儲需同時存儲該元素所在矩陣中的行標和列標。

例如，存儲圖 5 中的稀疏矩陣，需存儲以下信息：
? (1,1,1)：數據元素為 1，在矩陣中的位置為 (1,1)；
? (3,3,1)：數據元素為 3，在矩陣中的位置為 (3,1)；
? (5,2,3)：數據元素為 5，在矩陣中的位置為 (2,3)；
? 除此之外，還要存儲矩陣的行數 3 和列數 3；
由此，可以成功存儲一個稀疏矩陣。
注意，以上 3 種特殊矩陣的壓縮存儲，除了將數據元素存儲起來，還要存儲矩陣的行數值和列數值，具體的實現方式后續會介紹 3 種，本節僅需了解矩陣壓縮存儲的原理。
3. 矩陣壓縮存儲的 3 種方式
對于以上 3 種特殊的矩陣，對陣矩陣和上下三角矩陣的實現方法是相同的，且實現過程比較容易，僅需套用上面給出的公式即可。

稀疏矩陣的壓縮存儲，數據結構提供有 3 種具體實現方式：
? 三元組順序表；
? 行邏輯鏈接的順序表；
? 十字鏈表；
在Python中稀疏矩陣
SciPy提供了使用多種數據結構創建稀疏矩陣的工具，以及將稠密矩陣轉換為稀疏矩陣的工具。
許多在NumPy陣列上運行的線性代數NumPy和SciPy函數可以透明地操作SciPy稀疏數組。此外，使用NumPy數據結構的機器學習庫也可以在SciPy稀疏數組上透明地進行操作，例如用于一般機器學習的scikit-learn和用于深度學習的Keras。
存儲在NumPy數組中的稠密矩陣可以通過調用csr_matrix()函數將其轉換為一個稀疏矩陣。
在下面的例子中，我們將一個3×6的稀疏矩陣定義為一個稠密數組，將它轉換為CSR稀疏表示，然后通過調用todense()函數將它轉換回一個稠密數組。

dense to sparse

from numpy import array
from scipy.sparse import csr_matrix

create dense matrix

A = array([[1, 0, 0, 1, 0, 0], [0, 0, 2, 0, 0, 1], [0, 0, 0, 2, 0, 0]])
print(A)

convert to sparse matrix (CSR method)

S = csr_matrix(A)
print(S)

reconstruct dense matrix

B = S.todense()
print(B)
運行該示例首先打印已定義的稠密數組，接著是CSR表示，然后是重新構建的稠密矩陣。
[[1 0 0 1 0 0]
[0 0 2 0 0 1]
[0 0 0 2 0 0]]

(0, 0) 1
(0, 3) 1
(1, 2) 2
(1, 5) 1
(2, 3) 2

[[1 0 0 1 0 0]
[0 0 2 0 0 1]
[0 0 0 2 0 0]]
NumPy并沒有提供一個函數來計算矩陣的稀疏性。
不過，我們可以很容易地計算出矩陣的密度，然后從一個矩陣中減去它。NumPy數組中的非零元素可以由count_nonzero()函數給出，數組中元素的總數可以由數組的大小屬性給出。因此，數組的稀疏性可以被計算為：
sparsity = 1.0 - count_nonzero(A) / A.size
下面的例子演示了如何計算數組的稀疏性。

calculate sparsity

from numpy import array
from numpy import count_nonzero

create dense matrix

A = array([[1, 0, 0, 1, 0, 0], [0, 0, 2, 0, 0, 1], [0, 0, 0, 2, 0, 0]])
print(A)

calculate sparsity

sparsity = 1.0 - count_nonzero(A) / A.size
print(sparsity)
運行這個例子首先打印出定義的稀疏矩陣，接著是矩陣的稀疏性。
[[1 0 0 1 0 0]
[0 0 2 0 0 1]
[0 0 0 2 0 0]]

0.7222222222222222

參考鏈接：
https://zhuanlan.zhihu.com/p/34534763
http://data.biancheng.net/view/183.html
https://blog.csdn.net/yhb1047818384/article/details/78996906

總結

以上是生活随笔為你收集整理的稀疏矩阵理论与实践的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。