大型稀疏矩阵对存储和CPU要求高，很多集成化软件对于特大型矩阵的运算束手无策，因此需要一种优良的数据结构筛除稀疏矩阵中的0，从而实现数据的高效存储和运算。
对于m行n列的大型稀疏矩阵A（large sparse matrix），它大多数元素都为0，则可以使用三个一维数组存储该矩阵：A(k),JA(k),NA(n).每个数据的含义： **A(k)：**若A共有m*n个元素，其中有k个非零元素，每个非零元素按行存储，A(i)为第i个非零元素。 **JA(k)：**与数组A一样，有k个元素；JA(i)代表第i个非零元素在矩阵A的第JA(i)行。 **NA(n)：**共n个元素，NA(i)代表矩阵A的第i行有NA(i)个非零元素。 用图片表示更加直观： A = [ 0 a 12 a 13 … 0 a 21 a 22 0 … 0 ⋮ ⋮ 0 0 0 … a m n ] N A ( 1 ) = 2 N A ( 2 ) = 2 ⋮ N A ( n ) = 1 l = ∣ l 1 . . . l 2 ∣ l 1 . . l 2 ∣ . . . ∣ l 1 l 2 ∣ A = [ a 12 , a 13 , a 21 , a 22 , . . . , a m n ] J A = [ 2 , 3 , 1 , 2 , . . . , n ] A=\left [ \begin{array}{cccc} 0 & a_{12} & a_{13} & \dots & 0 \\ a_{21} & a_{22} & 0 & \dots & 0 \\ \vdots & & & & \vdots \\ 0 & 0 & 0 & \dots & a_{mn} \end{array} \right ] \quad \begin{array}{cccc} NA(1)=2\\ NA(2)=2 \\ \vdots \\ NA(n)=1 \end{array} \\ \quad \\ \quad \\ l= \; | \; l_1... l_2 \; \; | \;\; l_1.. l_2 \;| \; ... \;| \; l_1l_2 | \\ A=[a_{12},a_{13},a_{21},a_{22},...,a_{mn}] \\ JA=[2, \; \; \; 3, \; \; \;1, \; \; \; 2, \; \; ...\; \;,n] A=⎣⎢⎢⎢⎡0a21⋮0a12a220a1300………00⋮amn⎦⎥⎥⎥⎤NA(1)=2NA(2)=2⋮NA(n)=1l=∣l1...l2∣l1..l2∣...∣l1l2∣A=[a12,a13,a21,a22,...,amn]JA=[2,3,1,2,...,n]
其中，L1和L2是每行的第一个元素和最后一个元素。对于该矩阵的运算，示例的Ax乘法运算fortran代码如下：(A为m*n矩阵，x为长度为n的一维数组)
# this is fortran code to calculate Y=A*x # input:m,n,X(n); output:Y(m) # A is storted in common A(k),JA(k),NA(m) subroutine aprod(m,n,X,Y) interger m,n real X(n),Y(m) common A(9000),JA(9000),NA(1000) real sumtemp zero c initial parameter zero=0.0 l2=0 c every row of array A do 200 i=1,m sumtemp=zero l1= l2 + 1 l2= l1 + NA(i) c every non zero element of ith row c l1 is the first nonzero element, l2 is the last nonzero element do 100 l=l1,l2 j=JA(l) sumtemp=sumtemp+A(l)*X(j) 100 continue Y(i)=Y(i)+sumtemp 200 continue return本文内容引自Paige and Saunders 1982年的文章：[ALGORITHM 583] LSQR: sparse linear equations and least squares problems.
