Research On GPU-oriented Parallel Sparse Approximate Inverse Precondition Algorithm

How to construct efficient sparse approximate inverse preconditioners to accelerate the convergence of iterative method for solving linear equations is always of great importance in scientific computing.It is required to improve the efficiency of iterative solution of linear equations as the size of the matrices increases.It is found that although the sparse approximation inverse(SPAI)preconditioner can effectively improve the convergent rate of iterative methods,constructing them is very time-consuming.In recent years,with the development of the Graphics Processing Unit(GPU)and the maturity of its programming model Compute Unified Device Architecture(CUDA),how to design efficient sparse approximate inverse preconditioners based on GPUs has attracted much attention.In this context,on the basis of GPUs,this thesis makes in-depth research on how to accelerate the construction of efficient sparse approximate inverse preconditioners.The main work and contributions are summarized as follows:1.A parallel adaptive static SPAI preconditioning algorithm on GPU,called SPAI-Adaptive,is proposed.In SPAI-Adaptive,the sparse pattern of the preconditioner is predetermined.Here a sparse pattern method related to the coefficient matrix is used.Then,each component of the preconditioner which includes finding indices I and J,constructing local submatrix,decomposing the local matrix into QR,and solving the upper triangular linear system,is computed in parallel inside a thread group of GPU.In order to improve the parallel efficiency,an adaptive thread allocation strategy is proposed for any matrix.The experimental results show that SPAI-Adaptive proposed in this thesis is effective,and is superior to two popular sparse approximate inverse preconditioning algorithms and has better parallelism.2.A parallel dynamic SPAI preconditioning algorithm on GPU,called DFSPAI,is proposed.Compared with SPAI-Adaptive,the sparse pattern of DFSPAI is determined dynamically during the computing process.In DFSPAI,we first determines the upper limit for filling the non-zero elements of each column of the preconditioner,and set the initial preconditioner to a diagonal sparsity;Then the initial I,J,QR,m_k and r_k are computed;Furthermore,the corresponding non-zero positions of the preconditioner are filled based on r_k,the corresponding I,J,QR are updated,new m_k and r_k are computed until the residual norm is less than the predetermined threshold or the non-zero filled number exceeds the upper limit.The experimental results show that DFSPAI has good effectiveness.3.The two algorithms proposed in this thesis are compared by applying them to solve the practical sparse linear system Ax=b.On the one hand,the effectiveness of the sparse approximate inverse preconditioners constructed by the two algorithms is verified.On the other hand,the advantages and disadvantages of the two algorithms are analyzed from multiple perspectives.