以分級平行多層舒爾法於CUDA叢集解線性系統

Abstract

解稀疏線性系統是科學計算領域中最核心的問題之一，隨著問題的規模增加，有效率的解稀疏線性系統是必要的。在現今的計算機架構中，計算核心的時脈由於物理限制而難以大幅提升，計算單元的設計傾向以多核心平行達到提升效能的目的。為了最大化計算資源的使用以達到更高的效率，演算法必須針對平行的架構設計演算法。多層舒爾法藉由分析以多重巢狀分割法重排後稀疏矩陣的分塊結構，將矩陣直接解法的分解過程拆解為可平行的子問題，各個子問題中再適當地以不同的方法平行加速。在此之上，經由分析各個子問題的所需計算量，再以優化過的機制將子問題均衡的分配到不同的處理器上，進而達到更高的可擴展性。

Sparse linear system solver is one of the core of scientific computing. As the scale of problem increases, to solve sparse linear systems efficiently is necessary. In recent computer architecture, the frequency of computation core is bounded by physical limitations, thus current design of computatation unit as CPU and GPU use multiple cores to improve the performance. Hierarchical Schur method expolits the block structure of multilevel nested dissection reordered sparse linear system and decompose the direct matrix factorization scheme into concurrent subproblems. In each subproblems we properly applied different techniques for lower level parallelism. Moreover by analyzing the computation cost of each subproblems, it is able to distribute the computation load to different resources to improve overall scalability.