6.6 特殊矩阵的压缩存储在计算机科学中，用二维数组来表示数学中的矩阵，是最自然的方法。
所谓的压缩存储，从而可以提高存储空间利用率。就是有一类矩阵，其非零元素或者零元素的分布有一定规律，比如：对称矩阵、三角矩阵、对角矩阵等。为了节省存储空间，可以利用这类矩阵中元素的分布规律，为多个值相等的元素只分配一个存储空间，对零不分配空间。这就
1. 对称矩阵
对于 nnn 阶方阵 A=(aij)n×n\pmb{A}=(a_{ij})_{n\times n}A=(aij)n×n，位置索引值i=ji=ji=j的那些元素，构成了矩阵的主对角线（Main Diagonal）。
i=ji=ji=j ，aija_{ij}aij构成了主对角线元素；i
以主对角线为对称轴，两侧元素对称分布的对角矩阵，即aij=aji, i≠ja_{ij}=a_{ji},~i\ne jaij=aji,i=j，这样的矩阵称为对称矩阵（Symmetric Matrix），即上三角部分和下三角部分中的对应元素相等。
如果将对称矩阵存储到一维的存储结构中，为了讲解和操作方便，用一维数组表示一维的存储结构，在 6.5 节中已经讲解过，假设将一维数组保存到内存中，该数组的元素和内存中的存储单元一一对应。所以，能够假设一维数组BBB 作为 nnn 阶对称矩阵 A\pmb{A}A的存储结构，A\pmb{A}A 中的元素 aija_{ij}aij 存储在 BBB 中的 bkb_kbk 处。
在存储对称矩阵时，可以只存储主对角线和上三角部分的元素，或者是主对角线和下三角部分的元素，让对称的两个元素共享一个存储空间。
不失一般性，根据对称矩阵的特点，采用以行序为主序，存储主对角线和下三角部分的元素，如图 6.6.1 所示。
图 6.6.1 压缩对称矩阵下面探讨 kkk 与 i, ji,~ji,j 的关系（kkk是从 0 开始；i,ji,ji,j都是从 1 开始）。
（1）若 aija_{ij}aij 是 A\pmb{A}A中主对角线或下三角部分的元素，则有i≥ji\ge ji≥j（以行序为主序）。aija_{ij}aij 处于第 iii行，那么在第111 行到第 i−1i-1i−1行中，必须保存如下元素：
第 1 行有 1 个元素：a11a_{11}a11
第 2 行有 2 个元素：a21,a22a_{21}, a_{22}a21,a22
⋯\cdots⋯
第 i−1i-1i−1 行有 i−1i-1i−1 个元素：a(i−1)1,a(i−1)2,⋯ ,a(i−1)(i−1)a_{(i-1)1},a_{(i-1)2},\cdots,a_{(i-1)(i-1)}a(i−1)1,a(i−1)2,⋯,a(i−1)(i−1)
以上共计元素数量：1+2+⋯+(i−1)1+2+\cdots+(i-1)1+2+⋯+(i−1)
在第 iii 行的元素 aij (j≤i)a_{ij}~(j\le i)aij(j≤i)：就是的前面的元素ai1,ai2,⋯ ,ai(j−1)a_{i1},a_{i2},\cdots,a_{i(j-1)}ai1,ai2,⋯,ai(j−1) ，共计有 j−1j-1j−1 个元素综上，在 aija_{ij}aij：就是之前的元素总数量[1+2+⋯+(i−1)]+(j−1)=i(i−1)2+(j−1) [1+2+\cdots+(i-1)]+(j-1)=\frac{i(i-1)}{2}+(j-1)[1+2+⋯+(i−1)]+(j−1)=2i(i−1)+(j−1) 由于 kkk是从 0 开始，aija_{ij}aij 存储到 bkb_kbk 处，在 bkb_kbk 之前，数组 BBB 中共有 kkk个元素，对应矩阵A\pmb{A}A 中 aija_{ij}aij之前的元素，所以则有：k=i(i−1)2+(j−1), (i≥j)(1) k = \frac{i(i-1)}{2}+(j-1),~(i\ge j)\tag{1}k=2i(i−1)+(j−1),(i≥j)(1) （2）若 aija_{ij}aij 是 A\pmb{A}A中的上三角部分的元素，即i **重要方法归纳：**在计算矩阵A\pmb{A}A 中元素 aija_{ij}aij 在数组 BBB 中存储位置 kkk时，计算步骤如下： 求出元素 aija_{ij}aij前面共存放多少个元素，假设为mmm 个；注意数组 BBB存放元素的下标开始值，设下标开始值是sss（一般是从 0 开始，有的从 1 开始）。则 k=m+sk = m+sk=m+s 。 2. 三角矩阵 如果 nnn阶矩阵的下三角部分的元素均为常数ccc或零，那么该矩阵称为上三角矩阵（Upper Triangular Matrix）。同样，矩阵的上三角部分的元素均为常数ccc或零，该矩阵称为下三角矩阵（Lower Triangular Matrix）。 对三角矩阵进行压缩存储，除了存储上三角或下三角部分以及主对角线的元素之外，另外还要存储常数ccc。于是，可能采用存储对称矩阵的思想，但是要对数组BBB在末端增加一个位置，用以存储常数ccc 。 （1）下三角矩阵 假如将下三角部分和主对角线的元素，存储到一维数组BBB中，由对称矩阵的压缩存储可知，数组BBB中的元素个数是n(n+1)2\frac{n(n+1)}{2}2n(n+1) ，如果 BBB的下标是从 0 开始的，则最后一个元素的下标是n(n+1)2−1\frac{n(n+1)}{2}-12n(n+1)−1；再加上另一部分的常数ccc，则可知，若将三角矩阵压缩到一维数组BBB 中，需要 n(n+1)2+1\frac{n(n+1)}{2}+12n(n+1)+1个位置，即数组BBB：就是的下标范围0∼n(n+1)20\sim\frac{n(n+1)}{2}0∼2n(n+1)（含两端的值），如图 6.6.2 所示。 图 6.6.2 下三角矩阵下面分析，以行序为主序，将A\pmb{A}A 中的元素 aija_{ij}aij 存储到 BBB 的元素 bkb_kbk 中，kkk 和 i,ji,ji,j的关系，其中，kkk是从 0 开始，i,ji,ji,j是从 1 开始。 若 aija_{ij}aij 是 A\pmb{A}A中主对角线或下三角部分的元素，则有i≥ji\ge ji≥j。以行序为主序。 aija_{ij}aij 处于第 iii行，那么在第111 行到第 i−1i-1i−1行中，需要保存如下元素： 第 1 行有 1 个元素：a11a_{11}a11 第 2 行有 2 个元素：a21,a22a_{21}, a_{22}a21,a22 ⋯\cdots⋯ 第 i−1i-1i−1 行有 i−1i-1i−1 个元素：a(i−1)1,a(i−1)2,⋯ ,a(i−1)(i−1)a_{(i-1)1},a_{(i-1)2},\cdots,a_{(i-1)(i-1)}a(i−1)1,a(i−1)2,⋯,a(i−1)(i−1) 在第 iii 行的元素 aij (j≤i)a_{ij}~(j\le i)aij(j≤i)的前面的元素是：ai1,ai2,⋯ ,ai(j−1)a_{i1},a_{i2},\cdots,a_{i(j-1)}ai1,ai2,⋯,ai(j−1) ，共计有 j−1j-1j−1 个元素 综上，在 aija_{ij}aij之前的元素总数量：[1+2+⋯+(i−1)]+(j−1)=i(i−1)2+(j−1) [1+2+\cdots+(i-1)]+(j-1)=\frac{i(i-1)}{2}+(j-1)[1+2+⋯+(i−1)]+(j−1)=2i(i−1)+(j−1) 由于 kkk是从 0 开始，aija_{ij}aij 存储到 bkb_kbk 处，在 bkb_kbk 之前，数组 BBB 中共有 kkk个元素，对应矩阵A\pmb{A}A 中 aija_{ij}aij之前的元素，所以则有：k=i(i−1)2+(j−1), (i≥j) k = \frac{i(i-1)}{2}+(j-1),~(i\ge j)k=2i(i−1)+(j−1),(i≥j) 上三角部分的元素为常数ccc ，即 i 将以上两种情况合起来，得到kkk 与 i,ji,ji,j 的关系：k={i(i−1)2+(j−1),(i≥j)n(n+1)2,(i 对于上三角矩阵，也用类似的推导方法，得到kkk 与 i,ji,ji,j 的关系。 总结：当三角矩阵A\pmb{A}A中的元素下标编号是从 1 开始的时候，即i,ji,ji,j从 1 开始计数，但数组BBB 的 kkk从 0 开始（数组的一般规定），那么数组就是仍然BBB 的下标 kkk与三角矩阵的下标i,ji,ji,j的对应关系是：上三角矩阵k={(i−1)(2n−i+2)2+(j−i),(i≤j)n(n+1)2,(i>j)下三角矩阵k={i(i−1)2+j−1,(i≥j)n(n+1)2,(i 若一个 nnn 阶方阵 A\pmb{A}A满足其所有非零元素都集中在以主对角线为中心的带状区域中，则称此矩阵为nnn阶对角矩阵（Diagonal Matrix）。 对角矩阵主对角线上、下方各有bbb条非零元素构成的次对角线，称bbb矩阵半带宽，(2b+1)(2b+1)(2b+1)为矩阵的带宽。 对于半带宽为b (0≤b≤n−12)b~(0\le b\le\frac{n-1}{2})b(0≤b≤2n−1)的对角矩阵，其∣i−j∣≤b|i-j|\le b∣i−j∣≤b 的元素 aija_{ij}aij不为零，其余元素为零，即带宽之外的元素皆为零（如图 6.6.3 所示）。 图 6.6.3 对角矩阵如果 b=1b=1b=1，则得到如下所示的对角矩阵（为了显现清楚，这里以5×55\times55×5矩阵为例），该矩阵有一条主对角线和两条次对角线，故称为三对角矩阵。A=[a11a12000a21a22a23000a32a33a34000a43a44a45000a54a55] \pmb{A}=\begin{bmatrix}a_{11}&a_{12}&0&0&0\\a_{21}&a_{22}&a_{23}&0&0\\0&a_{32}&a_{33}&a_{34}&0\\0&0&a_{43}&a_{44}&a_{45}\\0&0&0&a_{54}&a_{55}\end{bmatrix}A=a11a21000a12a22a32000a23a33a43000a34a44a54000a45a55以三对角矩阵为例，对其以行序列主序进行压缩存储，只需要将其中的非零元素存储到一维数组BBB 中，aija_{ij}aij的对应存储位置是bkb_kbk ，kkk从 0 开始。 观察三角矩阵A\pmb{A}A，可以得知三角矩阵的如下特点： 行下标为 1 的行和行下标为nnn的行，都只有两个非零元素。其他行各有三个非零元素。对于行下标不为 1 的非零元素aija_{ij}aij，在其之前的非零元素包括： 行下标为 1 的行有 2 个非零元素； 从行下标 222 到行下标 i−1i-1i−1 的行，共计 i−2i-2i−2行，每行 3 个非零元素，共计3(i−2)3(i-2)3(i−2) 个元素 aija_{ij}aij所在行的行下标为iii ，aija_{ij}aij之前的元素可能是： 若 aija_{ij}aij是本行的第 1 个非零元素，则aija_{ij}aij之前的所有元素数量是：2+3(i−2)=3i−42+3(i-2)=3i-42+3(i−2)=3i−4。并且此时，必然有j=i−1j=i-1j=i−1 。所以 kkk 与 i,ji,ji,j 的关系为：k=3i−4=2i+i−1−3=2i+j−3 k = 3i-4=2i+i-1-3=2i+j-3k=3i−4=2i+i−1−3=2i+j−3 若 aija_{ij}aij是本行的第 2 个非零元素，则aija_{ij}aij：就是之前的所有元素数量2+3(i−2)+1=3i−32+3(i-2)+1=3i-32+3(i−2)+1=3i−3。并且此时，必然有i=ji=ji=j 。所以 kkk 与 i,ji,ji,j 的关系为：k=3i−3=2i+i−3=2i+j−3 k = 3i-3=2i+i-3=2i+j-3k=3i−3=2i+i−3=2i+j−3 若 aija_{ij}aij是本行的第 3 个非零元素，则aija_{ij}aij之前的所有元素数量是：2+3(i−2)+2=3i−22+3(i-2)+2=3i-22+3(i−2)+2=3i−2。并且此时，必然有j=i+1j=i+1j=i+1 。所以 kkk 与 i,ji,ji,j 的关系为：k=3i−2=2i+i+1−3=2i+j−3 k=3i-2=2i+i+1-3=2i+j-3k=3i−2=2i+i+1−3=2i+j−3 综上可知，对于三对角矩阵而言，压缩存储的时候，数组中的位置kkk 和矩阵的 i,ji,ji,j 关系是（i,ji,ji,j是从 1 开始，kkk从 0 开始）：k=2i+j−3(6) k=2i+j-3\tag{6}k=2i+j−3(6) 例 6.6.1若对 n 阶对称矩阵A\pmb{A}A 以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组 B[1..(n(n+1))/2] 中，则在 B 中确定 aij (i A. i×(i−1)/2+ji\times(i-1)/2+ji×(i−1)/2+j\qquad B. j×(j−1)/2+ij\times(j-1)/2+ij×(j−1)/2+i\qquad C. i×(i+1)/2+ji\times(i+1)/2+ji×(i+1)/2+j\qquad D. j×(j+1)/2+ij\times(j+1)/2+ij×(j+1)/2+i 【解】 矩阵 A\pmb{A}A 是 nnn阶对称矩阵，且元素aija_{ij}aij中的下标关系是i 根据以行序为主序的存储方式，存储对称矩阵的下三角（含对角线）不分，则第 1 行存储a11a_{11}a11；第 2 行存储a21,a22a_{21},a_{22}a21,a22 ；⋯\cdots⋯ ；第 (j−1)(j-1)(j−1) 行存储 a(j−1)1,⋯ ,a(j−1)(j−1)a_{(j-1)1},\cdots,a_{(j-1)(j-1)}a(j−1)1,⋯,a(j−1)(j−1) ；第 jjj 行存储 aj1,⋯ ,ajia_{j1},\cdots,a_{ji}aj1,⋯,aji。将各行所存储的元素个数求和：1+2+3+⋯+(j−1)+i=j×(j−1)2+i 1+2+3+\cdots+(j-1)+i=\frac{j\times(j-1)}{2}+i1+2+3+⋯+(j−1)+i=2j×(j−1)+i 所以，k=j(j−1)2+ik=\frac{j(j-1)}{2}+ik=2j(j−1)+i 。 本题答案：B