2.5 殊矩阵的压缩存储

2.5 特殊矩阵的压缩存储

　　矩阵是一种常见的数学对象，一般来讲，可以使用二维数组存储一个矩阵，但是数值分析中常常出现一些特殊的矩阵，例如，在某些矩阵中，相同值的元素或零值元素按照一定规律排列，则称此类矩阵为特殊矩阵。如果矩阵中存在大量的零值元素，而且零值元素的位置没有规律，则称此类矩阵为稀疏矩阵。如果对以上两类矩阵的存储采取相同值元素只存储一次，对零值元素不分配存储空间的策略，就可以节省大量的存储空间。这种存储策略称为特殊矩阵的压缩存储。

2.5.1 特殊矩阵

　　常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。
　　1．对称矩阵的压缩存储
　　对称矩阵是指上三角元素与下三角元素取值对应相等的矩阵，n阶对称矩阵满足以下条件：

a_ij=a_ji，1≤i,j≤n

　　可以使用一个只记载矩阵下三角元素的一维数组来存储对称矩阵，数组中的元素依次为（a₁₁，a₂₁，a₂₂，a₃₁，...a_m）如图2-6所示。

　　其中，矩阵元素a_ij的下标i、j与其存储在数组中的位置下标k（从0开始计数）存在如下的对应关系：在矩阵元素a_ij之前已经存储了i-1行矩阵元素和第i行的j-1个元素，又已知矩阵的第1行需要存储1个元素，第2行需要存储2个元素，以此类推，第i-1行需要存储i-1个元素，故矩阵元素a_ij之前一共存储的元素数有：

　　又由于数组下标从0开始，故矩阵元素a_ij存储在下标为的位置上。例如，矩阵元素a₃₁存储在一维数组中的位置为：

　　即一维数组中第4个元素。
　　2．三角矩阵的压缩存储
　　上（下）三角矩阵是指矩阵的下（上）三角元素取值相同，设此取值为常数C（一般为0），则三角矩阵只需存储常数C和上（下）三角中的数据元素即可。故其压缩存储方式与对称矩阵相同，只不过多出一个常数的存储空间，如图2-7所示。
　　3．对角矩阵的压缩存储
　　对角矩阵是指所有非零元素全部集中在中心几条对角线上的矩阵。下面以三对角矩阵（所有非零元素集中在中心三条对角线上）为例描述对角矩阵的压缩存储方法。图2-8是一个三对角矩阵，使用一维数组a[m]来压缩存储矩阵信息，则数组中的元素依次为a₁₁，a₁₂，a₂₁，a₂₂，a₂₃，a₃₂，...，a_m。

　　其中，矩阵元素a_ij的下标i、j与其存储在数组中的位置下标k（从0开始计数）存在如下的对应关系：当i=1时，k=j-1(1≤j≤2)；当i＞1时，k=2×i+j-3(|i-j|≤1)。推导方法如下：
　　① 当i=1时，j的取值就是矩阵元素a_ij在数组中的存储次序，数组中存储下标为次序减1，故k=j-1。
　　② 当i＞1时，在矩阵元素a_ij之前已经存储了i-1行矩阵元素和第i行的j-i+1个元素，又已知矩阵的第1行需要存储2个元素，第2～i-1行均需要存储3个元素，故矩阵元素a_ij之前一共存储的元素数有2+(i-1-2+1)×3+(j-i+1)=2×i+j-3。故aij的存储下标为2×i+j-3。
　　例如，矩阵元素a₃₃存储在一维数组中的位置为k=2×i+j-3=2×3+3-3=6，即一维数组中的第7元素。