LED算法

旋轉(zhuǎn)門算法除了平行四邊形算法之外，還能用三角形算法來表示。

圖遍歷算法

圖遍歷算法是最基本的圖算法之一，由指定節(jié)點開始，按照一定規(guī)則遍歷圖結(jié)構(gòu)中所有的連通節(jié)點，包括寬度優(yōu)先搜索(Breadth First Search,BFS)和深度優(yōu)先搜索(Depth First Search, DFS)等核心算法。

作為最基本的圖遍歷算法，寬度優(yōu)先搜索算法代表了圖遍歷算法的計算特性，具有非常重要的研究意義。一方面，BFS算法是最短路徑、鄰接查詢、可達(dá)性查詢等算法的實現(xiàn)基礎(chǔ)，廣泛應(yīng)用于圖分割、信念傳播統(tǒng)計以及網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)發(fā)現(xiàn)等領(lǐng)域;另一方面，BFS算法作為典型的數(shù)據(jù)密集型算法，體現(xiàn)了數(shù)據(jù)密集型應(yīng)用對高性能計算系統(tǒng)的需求，廣泛應(yīng)用于大規(guī)模并行計算系統(tǒng)的數(shù)據(jù)處理能力評測，已經(jīng)成為Parboil, Rodinia和Graph500等基準(zhǔn)測試程序的核心算法。

在實際應(yīng)用中，圖的規(guī)模在不斷增大，相應(yīng)的，對圖的存儲和處理開銷不斷增加，有效地實現(xiàn)大規(guī)模并行BFS算法具有十分重要的意義。

稀疏線性方程組求解法

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

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

一般來說，迭代法的求解速度高于直接法。但是，如果使用直接法時矩陣分解過程能夠被很多后續(xù)計算重復(fù)使用，則后續(xù)的三角陣求解可以非?？焖賹崿F(xiàn)，此時直接法在性能上具有優(yōu)勢。典型例子是模擬電路瞬態(tài)仿真，這時需要多次以Newton-Raphson方法求解非線性方程，每一次求解均會在工作點附近展開為線性方程，而且所有線性方程的矩陣分解方式都是固定的，因此求解該類問題最好的方法是直接法。稀疏矩陣的矩陣分解在GPU上的實現(xiàn)是很困難的，主要難點在于現(xiàn)有算法的數(shù)據(jù)依賴性導(dǎo)致可利用的并行性不足。此外，矩陣元素的排列順序?qū)τ嬎氵^程中間結(jié)果矩陣的非零元素個數(shù)有很大影響，同時矩陣分解后的非零元素的分布與原來矩陣可能很不相同。

迭代法的理論基礎(chǔ)相對復(fù)雜，并且具有多種不同的具體算法，但其基本形式均為從一個猜測解出發(fā)，通過多次迭代逐漸收斂，當(dāng)誤差滿足一定條件時迭代中止。共扼梯度法(CG)是迭代法的主流方法之一，特別適合于特征值為良態(tài)分布的對稱正定方程組；其它迭代法包括Jacobi、逐次超松弛(SOR)、廣義極小剩余(GMRES)、預(yù)條件共扼梯度(PCG)等。迭代法的核心算法是稀疏矩陣向量乘(SpMV)，因此實現(xiàn)SpMV的高效并行結(jié)構(gòu)也是實現(xiàn)迭代法的基礎(chǔ)。

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

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