工程计算中大型稀疏矩阵存储方法研究

RESEARCH ON THE STORAGE METHOD OF LARGE-SCALE SPARSE MATRIX IN ENGINEERING CALCULATION

在工程实际中,许多问题都可以归结为数值法求解偏微分方程（组）的问题.偏微分方程数值解法主要包括有限差分法、有限元法和有限体积法,其中大多数方法都是通过离散的方式将方程转化为线性方程组,通过求解线性系统得到原方程的数值解.在这个过程中,线性方程组的系数矩阵通常很大并且很稀疏,会占用大量存储空间并使方程组难以求解.针对这个问题,本文研究大型稀疏矩阵的压缩存储方法,只存储非零元素,降低存储空间消耗,避免零元素参与计算,提升计算效率.具体来说,在稀疏矩阵生成过程中,使用十字链表法存储,可以在常数时间内完成非零元素的插入操作;在方程组求解过程中,使用按行（列）压缩存储方法,既节约存储空间,又可以提高求解器的求解效率.在实验部分,本文分别使用有限差分法求解Laplace方程和有限元法计算圆环截面应力分布问题,对其中大型稀疏线性方程组的系数矩阵,采用十字链表法和按行（列）压缩存储法存储,使用直接法和迭代法求解线性方程组.实验结果显示,对于结构化和非结构化的稀疏矩阵,压缩存储方法不仅能够大幅度减少内存空间的占用,而且能够显著提升求解器的效率.

In engineering, many problems can be reduced to solve the partial differential equations（groups） with numerical methods. Numerical methods for solving partial differential equations include the finite difference method, finite element method and finite volume method.The core concept of these methods is to discrete the differential equations into a linear system, and the numerical solution of the original equations is obtained by solving the linear system. In this process, the coefficient matrix of the linear system is usually vary large and sparse, occupying large amounts of storage space and making the linear system difficult to solve. In order to alleviate the problem, this paper studies the compression storage method for large sparse matrix, which only stores non-zero elements. The strategy can reduce storage space and avoid zero elements to participate in calculation. In particular, in the process of generation of coefficient matrix, the insert operation of non-zero elements can be finished in constant time with the orthogonal list. In the process of solving, the Compression Storage Row/Column（CSR/CSC） can save storage space and improve the solver efficiency significantly. In experiment, we adopt the finite difference method to solve Laplace equation and use the finite element method to compute the stress distribution of the cross-section of a ring. For the linear systems, we use the orthogonal list and CSR/CSC to store the coefficient matrix, and use direct and iterative methods to solve the systems. Experimental results show that the compression storage method can not only greatly reduce the memory space for structured and unstructured matrices, but also can significantly improve the efficiency of the solvers.