稀疏矩陣算法

稀疏矩陣算法是以稀疏矩陣作為核心數據結構的算法。

稀疏矩陣算法的最大特點是通過只存儲和處理非零元素從而大幅度降低存儲空間需求以及計算複雜度，代價則是必須使用專門的稀疏矩陣壓縮存儲數據結構。稀疏矩陣算法是典型的不規則算法，計算訪存比很低，並且計算過程中的訪存軌跡與稀疏矩陣的稀疏結構相關。

稀疏矩陣算法是自然科學和社會科學中許多領域進行數值模擬計算時的關鍵技術和性能瓶頸，為了提高稀疏矩陣算法的計算性能，需要提高相應算法在特定平台上的計算效率。

基本介紹

• 中文名：稀疏矩陣算法
• 外文名：Sparse matrix algorithm
• 類別：控制科學與工程
• 特點：只存儲和處理非零元素
• 核心：稀疏矩陣
• 算法：圖遍歷算法等

算法概念

在科學與工程領域中進行數值計算時經常需要處理大型的稀疏矩陣，這些矩陣的特徵一是階數很大，二是含有大量的零元，使得無法使用傳統的稠密矩陣存儲方案和算法。由於矩陣階數太大，若存儲整個矩陣，將會占用大量的存儲空間，甚至會超出計算系統的存儲容量，因此需要設計專門的稀疏存儲方案，儘可能的減少零元素的存儲。

稀疏矩陣算法是以稀疏矩陣作為核心數據結構的算法。與稠密矩陣算法相比，稀疏矩陣算法的最大特點是通過只存儲和處理非零元素從而大幅度降低存儲空間需求以及計算複雜度，代價則是必須使用專門的稀疏矩陣壓縮存儲數據結構，因而在計算過程中引入了大量的離散間接定址操作。稀疏矩陣算法是典型的不規則算法，計算訪存比很低，並且計算過程中的訪存軌跡與稀疏矩陣的稀疏結構相關，很難發掘計算過程中的時空局部性，因此在傳統的基於Cache的處理器上稀疏矩陣算法的計算效率很低。為了提高稀疏矩陣算法的計算效率，需要從稀疏存儲數據結構和稀疏矩陣算法兩方面對現有算法進行改進。
按照套用領域的不同，稀疏矩陣算法分為兩類，一類是非數值計算算法，典型代表是圖搜尋算法，包括寬度優先搜尋等核心算法；另一類則是數值計算算法，典型代表是稀疏線性方程組求解，包括稀疏矩陣向量乘、稀疏三角方程組求解以及稀疏矩陣分解等核心算法。

算法

圖遍歷算法

圖遍歷算法是最基本的圖算法之一，由指定節點開始，按照一定規則遍歷圖結構中所有的連通節點，包括寬度優先搜尋(Breadth First Search,BFS)和深度優先搜尋(Depth First Search, DFS)等核心算法。
作為最基本的圖遍歷算法，寬度優先搜尋算法代表了圖遍歷算法的計算特性，具有非常重要的研究意義。一方面，BFS算法是最短路徑、鄰接查詢、可達性查詢等算法的實現基礎，廣泛套用於圖分割、信念傳播統計以及網路社區結構發現等領域;另一方面，BFS算法作為典型的數據密集型算法，體現了數據密集型套用對高性能計算系統的需求，廣泛套用於大規模並行計算系統的數據處理能力評測，已經成為Parboil, Rodinia和Graph500等基準測試程式的核心算法。
在實際套用中，圖的規模在不斷增大，相應的，對圖的存儲和處理開銷不斷增加，有效地實現大規模並行BFS算法具有十分重要的意義。

稀疏線性方程組求解法

稀疏線性方程組的求解是對自然科學和社會科學中許多實際問題進行數值模擬時的關鍵技術之一。在高層建築、橋樑、水壩、防洪堤的結構設計中，需對變形與應力情況進行模擬；在油氣資源探測與分析、數值天氣預報、飛行器的動力學分析中，需利用流體力學方程組進行模擬;在進行恆星大氣分析與核爆實驗時，常需利用輻射流體力學與粒子統計平衡等規律進行模擬。在對這些問題進行分析模擬時，通常利用偏微分方程建立數學模型。在對偏微分方程的離散求解過程中，稀疏線性方程組求解算法扮演著十分重要的角色。在許多不以偏微分方程建模的問題中，稀疏線性方程組求解同樣發揮了重要的作用。在空中交通控制、電力線路中的最優電流問題中，需利用數學規劃求解;在對採納某項政策時在某給定條件下對國內、國際多個區域的相應經濟指標進行預測時，需利用CGE模型進行分析；在可靠性分析、排隊網路分析與計算機系統性能評估中，常利用具有大量狀態的離散Markov鏈進行模擬。在這些問題的求解中，稀疏線性方程組的求解都占有重要位置，並且往往是整個計算過程中的性能瓶頸，稀疏線性方程組的高效求解是計算數學和工程套用中十分重要的課題之一。

解稀疏線性方程組的方法包括直接法(direct method)與疊代(iterative method)兩類。直接法指在不考慮計算捨入誤差的情況下，通過包括矩陣分解和三角方程組求解等有限步的操作求得方程組的精確解，因此又稱精確法;疊代法指給定一個初始解向量，通過一定的計算構造一個向量列(一般通過逐次疊代得到一系列逼近精確值的近似解)，向量列的極限為方程組理論上的精確解。疊代法對存儲空間的需求低，在求解高階非病態稀疏線性方程組方面具有一定優勢。然而，疊代法不適合求解病態問題，性能因問題而異，並且面臨精度控制、收斂速度慢或不收斂等問題。與疊代法相比，直接法的通用性好，求解結果精度高，性能穩定。當矩陣分解結果能夠被多次後續計算重用以及多右端項時，直接法的優勢尤其明顯。在有限元分析、模擬電路瞬態仿真等套用領域的商用軟體均採用直接法求解器作為標準的稀疏線性方程組求解器。但直接法的缺點在於對存儲資源要求較高，無法處理高階稀疏矩陣。

一般來說，疊代法的求解速度高於直接法。但是，如果使用直接法時矩陣分解過程能夠被很多後續計算重複使用，則後續的三角陣求解可以非常快速實現，此時直接法在性能上具有優勢。典型例子是模擬電路瞬態仿真，這時需要多次以Newton-Raphson方法求解非線性方程，每一次求解均會在工作點附近展開為線性方程，而且所有線性方程的矩陣分解方式都是固定的，因此求解該類問題最好的方法是直接法。稀疏矩陣的矩陣分解在GPU上的實現是很困難的，主要難點在於現有算法的數據依賴性導致可利用的並行性不足。此外，矩陣元素的排列順序對計算過程中間結果矩陣的非零元素個數有很大影響，同時矩陣分解後的非零元素的分布與原來矩陣可能很不相同。

疊代法的理論基礎相對複雜，並且具有多種不同的具體算法，但其基本形式均為從一個猜測解出發，通過多次疊代逐漸收斂，當誤差滿足一定條件時疊代中止。共扼梯度法(CG)是疊代法的主流方法之一，特別適合於特徵值為良態分布的對稱正定方程組；其它疊代法包括Jacobi、逐次超鬆弛(SOR)、廣義極小剩餘(GMRES)、預條件共扼梯度(PCG)等。疊代法的核心算法是稀疏矩陣向量乘(SpMV)，因此實現SpMV的高效並行結構也是實現疊代法的基礎。

直接法由高斯消元法發展向來，求解過程包括矩陣排序(matrix ordering)符號分解(symbolic factorization)、數值分解(numerical factorization)、三角方程組求解((triangular solves)四個步驟。其中，矩陣排序和符號分解屬於預處理部分。矩陣排序通過啟發算法置換稀疏矩陣的行列，試圖在後續計算中維持矩陣的稀疏性或數值穩定性。符號分解則是預先對矩陣分解後的稀疏結構進行預測，預先分配存儲空間並記錄數據相關性。直接法的計算瓶頸在於數值分解部分和三角方程組求解部分，高效的直接法求解依賴於二者的高效實現。

對於一個稀疏線性方程組是選擇直接法還是疊代法求解，一般有如下原則：對於低階矩陣或大型帶狀矩陣所對應的線性方程組，用直接法求解；而對於大型(非帶形)矩陣所對應的線性方程組，用疊代方法求解。實際上，選用何種方法還要看具體的套用背景，比如，對於線性規劃和一些結構工程套用，只有直接法是切實可行的。對於精度要求很高的問題，還可以採用由直接法得到初始解再用疊代法進行疊代的方法求解，這種方法稱為疊代精化法。

挑戰

面向算法加速器的稀疏矩陣算法並行化方法

由於算法加速器採用了與通用處理器完全不同的體系結構和編程模型，因此需要專門設計針對算法加速器的並行程式。與通用處理器相比，算法加速器能夠運行更多的執行緒，因此一方面需要將計算任務劃分為更多的子任務，實現細粒度並行；另一方面需要考慮執行緒間的負載均衡和數據局部性，特別是執行緒間的通信和同步開銷。與通用處理器相比，算法加速器更容易受到不規則訪存和計算的影響，因此必須通過矩陣預處理等手段提高計算的規則性和數據的局部性。

通用處理器與算法加速器協同計算策略

異構體系結構的計算單元包括通用處理器和算法加速器兩部分。在學術研究中通常分別針對這兩種計算單元設計並行算法，但在實際套用中，需要同時利用計算系統的所有計算資源以獲取最高性能。然而，現有的針對通用處理器和算法加速器的並行算法分別採用了不同的編程模型和最佳化策略，無法直接互相遷移，並且在協同計算過程中，不但需要在兩個平台上都能高效運行的並行程式，而且需要實現通信與計算的重疊以隱藏數據傳輸的開銷，這些都要求對現有的算法針對異構平台進行重新設計。

面向稀疏結構特徵的數據結構和算法映射

不同套用領域的稀疏矩陣往往具有不同的稀疏結構特徵，這些特徵因問題而異；具有不同稀疏結構特徵的稀疏矩陣往往對應不同的最優存儲方案以及不同的並行算法實現。在計算過程中，對於稀疏矩陣算法的不同計算階段，會因稀疏結構導致的計算特徵的不同而適合在通用處理器或算法加速器上運行或是由二者協同計算。因此，研究矩陣的稀疏結構並設計相應的數據結構和算法映射策略，能夠有效提高算法對於不同矩陣和不同計算平台的適應性。