為甚麼間接儲存零?
假設每行代表一位用戶,每列代表一種可能的商品。每位用戶只接觸少數商品,但商品總數非常大。稠密表格要為每個用戶與商品的組合分配位置,連沒有發生的組合也不例外。最小二乘和許多迭代算法都需要矩陣向量乘積,因此我們希望只存取已儲存的項目,而不是掃描整個表格。
本節使用壓縮稀疏行(CSR)格式。稀疏描述的是矩陣及其表示方式,並不保證後續結果也稀疏。設 是 實矩陣,,。陣列索引從 0 開始;區間 包含 而不包含 。先討論精確算術,浮點累加及硬件成本需另行衡量。
三個陣列及其不變量
這種表示由三個陣列,以及把它們與矩陣聯繫起來的不變量組成。
定義 4.4.1
(CSR 表示)
一個存有 個項目的 矩陣的 CSR 表示,由長度為 的陣列 value、col 和長度為 的陣列 rowptr 組成,並滿足以下不變量:
rowptr[0] = 0,rowptr[m] = s,指標均為非遞減整數;- 對第 行半開區間
[rowptr[i], rowptr[i+1])中的位置 ,col[k]是 中的整數,value[k]是第 行的一個貢獻。
所表示的矩陣為
其中空和為零。空行的兩個相鄰指標相等。
這個約定容許同一行重複列索引,也容許儲存明示的零; 是儲存項目數,不一定是數學上非零元素的個數。程式庫對 CSR 規範格式的定義並不完全相同:一種常見約定要求每行列索引有序、重複項已合併,但仍可儲存明示的零。再刪除這些零,便得到更嚴格的無零表示。這些約定便於比較和某些運算,但排序、合併及刪除零也有建構成本。以下乘法不要求規範次序。
常見錯誤
(把一行的指標區間當作閉區間)
第 行擁有從 rowptr[i] 起、但不包括 rowptr[i+1] 的位置。若 rowptr = (0, 2, 2, 4),第 行只擁有位置 和 。若迴圈也訪問位置 rowptr[i+1],第 行便會取得屬於第 行的位置 ,空的第 行也會看似非空。正是半開約定使相鄰各行恰好劃分位置 。
定理 4.4.2
(用同一份儲存計算正向與轉置乘積)
給定有效 CSR 陣列,將 和 初始化為零。遍歷每行 的每個儲存位置 ,向 加入 value[k] * x[col[k]],並向 加入 value[k] * y[i]。結束時 ,;重複列和空行也適用。
證明
(重新分組已儲存的貢獻)
固定行 ,算法所得為
第二個等號將有限和按列分組,並應用表示不變量。同理,固定列 ,分散累加得到
這正是 和 的各個座標。空和貢獻零。證明不依賴行內儲存次序;不過浮點算術中改變次序可能改變捨入結果。
兩個計算其實是同一個有限和,只是以兩種方式分組。
證明透視
證明用到不變量的哪些部分
指標條件使各行區間恰好劃分位置 ,因此每個儲存貢獻都恰好被訪問一次,並歸入正確的行;col 的範圍條件則保證每次讀取 、每次寫入 都合法。關鍵一步是重新分組一個以儲存位置為指標的有限和:按行分組得到 的座標,按列分組得到轉置乘積的座標。重複的列索引毋須特別處理,因為所表示矩陣的定義本來就把它們相加,而重新分組也以同樣方式相加。論證利用精確加法的交換律與結合律來忽略訪問次序;在浮點運算中失效的正是這一步,次序改變可能改變捨入後的和。
例題 4.4.3
(空行與兩個乘積)
令
第二行對應空區間 。取 ,逐行求和得到 。取 ,把各行貢獻散加到列,得到 。由於第二行為空, 的第二個座標沒有影響。可用內積檢驗: 與 都等於 。
概念視角結構
同一組陣列按列儲存了轉置
把三個陣列中行與列的角色互換來讀:rowptr 成為列指標陣列,col 成為行索引陣列。它們便構成 矩陣 的壓縮稀疏列(CSC)表示,因為第 行中的位置 把 value[k] 計入 的 元。因此毋須另存轉置副本。正向乘積沿每個已存行收集,而轉置乘積正是這個 CSC 矩陣逐列分散累加的自然做法,所以它的寫入可能互相衝突。
儲存項目與非零元素可以不同,下面的邊界情況說明這點。
例題 4.4.4
(互相抵消的重複項)
對一個 矩陣,設 rowptr = [0, 2, 2, 3],col = [1, 1, 3],value = [2, -2, 5]。第 行擁有位置 ,兩者都在列 ,故 。第 行對應空區間 。第 行擁有位置 ,故 。因此數學上只有一個非零元素,雖然儲存了 個項目。乘法算法仍給出正確答案:對 ,它算出 、、。合併重複項並刪除零後,只剩一個儲存項目。
實作與成本
以下函數假設數據入口已經驗證 CSR 不變量。它只遍歷一次儲存數據,返回稠密輸出向量,包括仍為零的座標;不會暗中排序或合併重複項。在一般 Python 中,0.0 初始化使累加使用浮點運算,即使輸入是整數也可能捨入;精確算術定理描述的是基礎運算,並非這段程式碼的逐位精確保證。
def csr_products(m, n, rowptr, col, value, x, y):
forward = [0.0] * m
transpose = [0.0] * n
for i in range(m):
for k in range(rowptr[i], rowptr[i + 1]):
j = col[k]
a = value[k]
forward[i] += a * x[j]
transpose[j] += a * y[i]
return forward, transpose
命題 4.4.5
(CSR 乘積的成本)
在隨機存取、單位操作成本模型下,csr_products 需 時間,輸出另需 額外空間。CSR 陣列本身佔 個元素。
證明
(計算迴圈次數)
初始化輸出需要 次寫入。外層迴圈執行 次,第 行的內層迴圈執行 rowptr[i+1] - rowptr[i] 次。這些次數相加後逐項相消,得到 rowptr[m] - rowptr[0] ,所以只做常數工作的內層主體總共執行 次。總成本為 。唯一的新儲存是兩個輸出串列,大小分別為 和 ;CSR 陣列的長度則為 、 和 。
稠密輸入則需要 個元素。這裏計算元素而非位元組:數值和索引的位寬、記憶體對齊都會影響實際空間。輸入向量共需 個元素;上述成本不包括建構、驗證、磁碟讀寫、通訊及裝置間傳輸。若 接近 ,索引開銷可能使 CSR 不划算。若 極大,即使遍歷很少的項目,初始化稠密轉置輸出也可能佔主要成本。
若每個工作執行緒負責不同輸出行,按行計算正向乘積比較容易平行化。轉置乘法則不同:不同的行可能寫入同一列,不同步的平行更新可能丟失貢獻。應使用適當的歸約、原子操作或按列儲存,並計入相應記憶體、通訊和浮點次序的影響。這些都需要實際設計,不能僅由稀疏性保證。
常見錯誤
(像正向乘積一樣平行化轉置乘積)
設兩行各在列 有一個儲存項目,數值分別為 和 ,且 。正確座標為 。若兩個執行緒都先讀到初值 ,各自計算後不同步地寫回,一次寫入可能覆蓋另一次,最終只剩 或 。按行分工對正向乘積安全,只因每行寫入自己的輸出座標;轉置乘積則需要歸約或原子更新。
反例模式
稀疏輸入不代表每個中間結果都稀疏
設 是一個 矩陣,第一行為 ,其餘元素為零。它在 個位置中只有 個非零元素,但 有 個非零元素。因此明確建構 可能破壞儲存優勢。計算 時,兩次稀疏乘法可以避免儲存這個稠密中間矩陣;這本身並不能改善條件數,也不能證明某個求解器收斂。
這種兩遍計算在小例子上很容易實行。
例題 4.4.6
(以兩次稀疏遍歷取代稠密中間矩陣)
在上面的矩陣中取 ,於是 rowptr = [0, 3, 3, 3]、col = [0, 1, 2]、value = [1, 1, 1],並令 。正向遍歷給出 。以 作轉置遍歷,把 散加到每一列,得到 。直接計算, 是 全一矩陣,。兩次遍歷各只觸及 個儲存項目,從未儲存 的 個元素。
練習與解答
快速檢查
(對第一個例題中的矩陣,計算 時的 。)
把每行已儲存的貢獻相加。
解答 · 答案
三行的和分別為 、空行的 和 ,所以 。
快速檢查
(寫出 不含重複項、不儲存零的 CSR 陣列。)
逐行列出非零元素。
解答 · 答案
第 行在列 有 ,第 行在列 有 。因此 value = [7, 1]、col = [2, 0]、rowptr = [0, 1, 2];此時 ,且 rowptr[2] = s,符合要求。
快速檢查
(矩陣有 行、 列和 個儲存項目。行指標陣列有多少項?函數的時間界計算了甚麼?)
利用定義中的長度和成本命題。
解答 · 答案
rowptr 有 項。時間界 計算初始化、行遍歷和儲存項目上的基本操作,並非耗時預測,也不包括建構陣列的成本。