GPU并行的大規(guī)模稀疏近似逆預條件算法研究.pdf

1、稀疏近似逆預條件子應用到迭代法中已證明其有效性。然而，獲得這些預條件子的計算復雜度往往較高，面對大規(guī)模問題時顯得力不從心，需要加速。近些年來，隨著高計算能力的圖形處理器(graphics processor unit,GPU)的興起，用于大規(guī)模問題的GPU加速的并行稀疏近似逆預條件子已引起廣泛的關注。因此，本文針對共軛梯度(conjugate gradient，CG)算法，基于對稱超松弛(symmetric successive ove

2、r-relaxation,SSOR)預條件子和一種近似逆(approximate inverse,AINV)算法，研究構造GPU架構下高效并行的稀疏近似逆預條件子。
　　本文所做的工作和貢獻如下：
　　1.由于SSOR預條件共軛梯度算法中預條件方程求解需要強串行的前推和回代，導致算法遷移到GPU平臺上并行效率不高。為此，基于諾依曼(Neumann)多項式分解技術，提出了一種GPU加速的SSOR稀疏近似逆預條件子(GSSORS

3、AI)。它不僅保持了原線性系統(tǒng)系數矩陣的稀疏和對稱正定特性，而且預條件方程求解僅需一次稀疏矩陣矢量乘運算，避免了前推和回代過程。實驗結果表明，在NVIDIA Tesla C2050 GPU上，對比使用Python在單個CPU上SSOR稀疏近似逆預條件子實現方法，GSSORSAI平均快將近100倍；應用到并行的PCG算法中，相比無預條件的CG算法，平均提高了3倍的收斂速度。
　　2.由于SSOR稀疏近似逆預條件子需要對稱正定線性系統(tǒng)

4、的系數矩陣A滿足P(-D-1L)<1，所以接著針對一般性的對稱正定矩陣A，基于AINV算法，利用圖劃分技術對原始矩陣A做分塊，通過對子圖做內點和邊界點的區(qū)分，以及稀疏矩陣的置換技術，將矩陣A的稀疏近似逆轉換成分塊箭型矩陣的稀疏近似逆。進而，利用GPU的多支流處理器，改進了稀疏矩陣乘ESC算法，實現了一種高效并行的稀疏AINV預條件子。實驗證明，基于GPU的AINV稀疏預條件子高度并行，并且應用到PCG（preconditioned co