在科學與工程計算、機器學習、圖形學等眾多領域中，矩陣是一種基礎且重要的數據結構。當矩陣中非零元素（或特定值元素）的數量遠少于零元素（或默認值元素）的數量時，我們稱之為“稀疏矩陣”。例如，一個1000×1000的矩陣中，可能只有不到1%的元素是非零的。如果使用傳統的二維數組來存儲這樣的矩陣，將浪費大量的存儲空間來存放零值，并且在運算時也會進行大量無效的零值操作，效率低下。因此，針對稀疏矩陣，發展出了一系列高效的壓縮存儲方法。

一、 稀疏矩陣的定義與特性

稀疏矩陣沒有嚴格的數學定義。通常，當一個矩陣的稀疏度（非零元素個數與總元素個數的比值）低于一個經驗閾值（例如5%或0.5%）時，就可以認為是稀疏的。其核心特性是：

1. 大量重復值：絕大多數元素是相同的（通常是零）。
2. 分布不規則：非零元素在矩陣中的位置沒有固定的規律。

正是這些特性，使得我們可以放棄存儲每一個元素，轉而只存儲非零元素的值及其位置信息，從而達到壓縮的目的。

二、 主要的壓縮存儲方法

1. 三元組順序表（COO - Coordinate Format）

這是最直觀的壓縮方法。我們使用三個一維數組來分別存儲：

• data：所有非零元素的值。
• row：每個非零元素對應的行號（從0或1開始）。
• col：每個非零元素對應的列號。

示例：
對于一個矩陣：
[ 1 0 0 ]
[ 0 0 5 ]
[ 0 2 0 ]
其三元組表示為（假設行、列索引從0開始）：
data = [1, 5, 2]
row = [0, 1, 2]
col = [0, 2, 1]

優點：結構簡單，容易構造，適用于非零元素隨機分布的矩陣。
缺點：不便于進行矩陣運算（如轉置、乘法），因為訪問特定行或列需要遍歷整個數組。

2. 壓縮稀疏行（CSR - Compressed Sparse Row）

這是最常用、最高效的通用稀疏矩陣存儲格式之一。它同樣使用三個數組：

• data：所有非零元素的值，按行優先順序排列。
• indices：每個非零元素對應的列號。
• indptr（或row_ptr）：行指針數組。其長度為行數+1。indptr[i]表示第i行第一個非零元素在data和indices中的起始索引，indptr[i+1]是其結束索引。因此，第i行的非零元素存儲在data[indptr[i]: indptr[i+1]]中。

示例（同上矩陣）：
data = [1, 5, 2] // 第一行的1，第二行的5，第三行的2
indices = [0, 2, 1] // 分別對應的列號
indptr = [0, 1, 2, 3] // 第0行從索引0開始（有1個元素），第1行從索引1開始（有1個元素），第2行從索引2開始（有1個元素），結束于3。

優點：高效支持按行訪問、矩陣-向量乘法等操作。內存訪問模式連續，緩存友好。
缺點：構建和修改（插入/刪除非零元）成本較高。

3. 壓縮稀疏列（CSC - Compressed Sparse Column）

CSC是CSR的列優先版本，原理完全相同，只是將“行”換成了“列”。它使用：

• data：所有非零元素的值，按列優先順序排列。
• indices：每個非零元素對應的行號。
• indptr：列指針數組。

優點：高效支持按列訪問、向量-矩陣乘法、矩陣轉置（CSR轉CSC即相當于轉置）等操作。

三、 專用格式

除了上述通用格式，還有一些針對特殊稀疏模式的格式：

• 對角線存儲（DIA）：適用于非零元素集中分布在主對角線及其附近幾條對角線上的矩陣（如某些偏微分方程離散化產生的矩陣）。
• ELLPACK（ELL）：適用于每行非零元素數量大致相同的GPU計算。
• 塊壓縮存儲（BSR）：當非零元素呈小塊狀聚集時，將每個小塊視為一個“元素”進行存儲，可以提高緩存利用率和特定運算性能。

四、 應用與庫支持

在編程實踐中，我們通常不會手動實現這些結構，而是使用成熟的科學計算庫：

• SciPy（Python）：scipy.sparse 模塊提供了 coo<em>matrix, csr</em>matrix, csc<em>matrix, dia</em>matrix 等多種格式，并能高效地進行轉換和運算。
• Eigen（C++）：提供了稀疏矩陣模塊。
• MATLAB：內置了稀疏矩陣類型及相關算法。

五、

稀疏矩陣的壓縮存儲是平衡空間與時間效率的關鍵技術。選擇哪種格式取決于：

1. 矩陣的非零模式（行變化大、列變化大、對角線、塊狀？）。
2. 主要的操作類型（頻繁按行訪問、按列訪問、轉置、構建？）。
3. 硬件平臺（CPU/GPU？對緩存是否敏感？）。

理解這些核心格式的原理，有助于我們在處理大規模稀疏數據時，選擇合適的工具和策略，從而設計出高效、節省內存的算法與程序。