Research And Application Of Large-scale Sparse Matrix Approximate Inverse Sparse Mode

In the field of scientific computing,the efficient solution of sparse linear equations has always been an important issue for researchers.With the improvement of computer computing power,people have higher expectations for the depth and breadth of the problem,and it is required to improve the iterative solution efficiency of sparse linear equations.It is well known that the static sparse approximation inverse preconditioner based on the F-norm can effectively improve the convergence of the iterative algorithm.However,when constructing this type of preconditioner,it is important to specify its sparse pattern in advance.Using the characteristic polynomial expansion of the matrix,a good approximate inverse sparse pattern of the matrix can be obtained.However,as the size of the matrix increases,this acquisition method faces two challenges: 1)When the polynomial expansion coefficient is greater than or equal to 2,the sparse pattern obtained is no longer sparse;2)It will be very time-consuming to power the sparse matrix.Based on this background,this thesis is GPU-oriented,starting from the characteristic polynomial of the matrix,and has conducted an in-depth study on the construction of efficient sparse approximation inverse sparse pattern.The main work and contributions of this thesis are as follows:(1)A GPU-based sparse matrix-matrix multiplication algorithm with a sparse strategy is proposed.Aiming at the problem that Sparse Matrix-Matrix Multiplication(SPMM)cannot guarantee the sparseness of the output matrix,a sparse filtering strategy based on Gaussian distribution is proposed,which is then oriented to GPU and combined with the matrix multiplication pattern of merging by row.A parallel SPMM algorithm with sparsity is proposed.This algorithm can not only deal with the problem of sparse matrix multiplication efficiently,but also filter the elements in the product matrix through the sparse screening strategy to achieve the purpose of sparse product matrix.Experiments prove that the algorithm proposed in this thesis is effective,with high performance and good parallelism.(2)Several effective sparse matrix approximate inverse sparse patterns based on matrix characteristic polynomials are proposed.Based on the GPU-based sparse matrix-matrix multiplication algorithm with sparseness strategy proposed in(1),starting from the characteristic polynomial of the matrix,through the derivation and expansion of characteristic polynomials,several effective sparse matrix approximate inverse sparse patterns are obtained.The experimental results show that for any given sparse matrix,the sparse matrix approximate inverse sparse patterns obtained in this thesis is similar to the sparse pattern obtained after the sparseization of the inverse of the sparse matrix.(3)Apply the obtained sparse matrix approximate inverse sparse patterns to verify its effectiveness.Firstly,several effective sparse matrix approximate inverse sparse patterns based on matrix characteristic polynomials proposed in this thesis are applied to a static sparse matrix approximate inverse solving algorithm to obtain the sparse matrix approximate inverse;secondly,the obtained sparse matrix approximate inverse is taken as preconditioner,transferred to Biconjugate Gradient Stabilized Method(BICGSTAB)to solve the linear equations,and compare the pros and cons of each sparse pattern.The experimental results show that the sparse patterns proposed in this thesis is effective,and the sparse approximate inverse preconditioner obtained by it can greatly improve the convergence of the iterative algorithm.