三角矩阵和对称阵的压缩存储

矩阵的存储

• 对于多维数组，有两种映射方法：按行优先和按列优先。
  $$A_n=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right)$$

• 以二维数组为例

  • 按行优先存储的基本思想是：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。对于上述$A_n$,存储顺序为$a_{11},a_{12},\cdots ,a_{nn}$
    • 设二维数组的行下标与列下标的范围分别为$[0,h_1,],[0,h_2]$，则存储结构关系式为$\mathrm{Loc}({\mathrm{a}}_{\mathrm{ij}})=\mathrm{Loc}({\mathrm{a}}_{00})+(\mathrm{i}({\mathrm{h}}_2+1)+\mathrm{j})\mathrm{L}$
  • 按优先存储,存储顺序为$a_{11},a_{21},\cdots ,a_{nn}$
    • $\mathrm{Loc}({\mathrm{a}}_{\mathrm{ij}})=\mathrm{Loc}({\mathrm{a}}_{00})+(\mathrm{j}({\mathrm{h}}_1+1)+\mathrm{i})\mathrm{L}$
  • 其中$[i(h_2+1)+j]$,$[j(h_1+1)+i]$是偏移数组首地址的元素数量,再乘以单个元素所占存储单元数$L=\mathrm{sizeof}(\mathrm{ElemType})$,即可得到$\mathrm{Loc}({\mathrm{a}}_{\mathrm{ij}})$

对称矩阵

对称矩阵的定义及其存储方式。

对称矩阵是指一个 $n$ 阶矩阵 $A$ 中的任意一个元素 $a_{ij}$ 都有 $a_{ij}=a_{ji}$（$1\le i,j\le n$），即矩阵与其转置相等。对称矩阵的元素可以划分为三个部分：上三角区、主对角线和下三角区。

对于 $n$ 阶对称矩阵，上三角区的所有元素和下三角区的对应元素相同。若仍采用二维数组存放，则会浪费几乎一半的空间。因此，可以将 $n$ 阶对称矩阵 $A$ 存放在一维数组 $B[n(n+1)/2]$ 中，即元素 $a_{ij}$ 存放在 $b_k$ 中。比如只存放下半部分（含主对角线）的元素。

在数组 $B$ 中，位于元素 $a_{ij}$（$i\ge j$）前面的元素个数为：

• 第 $1$ 行：$1$ 个元素（$a_{1,1}$）。
• 第 $2$ 行：$2$ 个元素（$a_{2,1},a_{2,2}$）。
• ……
• 第 $i-1$ 行：$i-1$ 个元素（$a_{i-1,1},a_{i-1,2},\cdots ,a_{i-1,j-1}$）。
• 第 $i$ 行：$j-1$ 个元素（$a_{i,1},a_{i,2},\cdots ,a_{i,j-1}$）。

因此，元素 $a_{ij}$ 在数组 $B$ 中的下标 $k=1+2+\cdots +(i-1)+j-1$=$i(i-1)/2+j-1$（数组下标从 $0$ 开始）

即$k(i,j)$=$i(i-1)/2+j-1$,$(i⩾j)$(1)

上面讨论的是下三角内$a_{ij}$,$(i⩾j)$条件下的$i,j,k$关系式,给出了$a_{ij},(i⩾j)$存储到B中的位置索引$k$,即$B[k]=a_{ij}$,

在压缩对称阵的时候,可以仅遍历矩阵的下三角形以及主对角线部分的元素;上三角部分的元素不用遍历,就可以存储这个矩阵的元素的完整信息,可以无损解压出来

那么$i<j$的情况下$i,j,k$之间的关系又是如何?或者说若$a_{ij},(i<j)$时$a_{ij}$对应于数组B中的索引为$k$的元素,那么$k,i,j$之间满足什么关系

注意到对称矩阵的特点:$a_{i,j}=a_{j,i}$,这样就可以将$i<j$的情况转换到$i>j$的情况

当$i<j$时$j>i$,所以$a_{ji}$满足公式(1)的条件,$k(j,i)$=$j(j-1)/2+i-1$,$(j>i)$

综上元素下标$i,j,k$之间的对应关系如下：
$$k=\{\begin{array}{ll}\frac{i(i-1)}{2}+j-1,& i⩾j\\ \frac{j(j-1)}{2}+i-1,& i<j\end{array}$$
对称阵和其他特殊矩阵不同,对称阵上三角按列优先存储和下三角按行优先存储到一维数组B时序列是一样的;

因此对称阵中遇到上三角案列优先存储的问题,可以考虑转换为对应的按行优先存储的情况来解决,并且,无论哪种存储,$a_{ij}$=$a_{ji}$,当$i>j$时总是可以考虑转换为$a_{ji}$来处理

对于对称阵上三角按列优先存储,$a_{ij}$存储在$B[k]$,则$k=1+2+\cdots +(j-1)+i-1$=$\frac{1}{2}j(j-1)+i-1$,$(i⩽j)$,$k=\frac{1}{2}i(i-1)+j-1$,$(i>j)$

例如$a_{7,2}$,$k=\frac{1}{2}\times 7\times 6+1$=22

三角阵

和对称阵的压缩类似,以下三角为例,将元素的下三角和住对角线元素压缩到数组,但是上三角部分元素都是相同且无法通过下三角矩阵推出,需要存储到数组中,对于$n$阶三角阵,压缩需要的一维数组长度为$\frac{1}{2}n(n+1)+1$,比对称真要多1

三角阵的压缩

• 三角矩阵(方阵)$A[\mathrm{1...}n][\mathrm{1...}n]$,包括
  • 上三角矩阵(下三角所有元为同一个常量)$j⩽i$
  • 下三角矩阵(上三角所有元素为同一个常量)$i⩽j$
• $上下三角包含\frac{n(n+1)}{2}个元素;在加上(占据矩阵其余位置的)一个常量c$
• $所以需要一个大小\underline{至少}为\frac{n(n+1)}{2}+1维的数组来保存必要元素$
  • $A[1,...,n][1,...,n];B[\mathrm{1...}\frac{1}{2}n(n+1)+1]$

下三角矩阵

按行优先

推到过程和存储下三角对称阵过程几乎一样
$$k=\{\begin{array}{ll}\frac{i(i-1)}{2}+j-1,& i⩾j\\ \frac{1}{2}n(n+1),& i<j\end{array}$$
这里$i<j$的情况是上三角中的元素,上三角中的元素都存储在B[0...n(n+1)/2]中的最后一个元素中,索引为$\frac{1}{2}n(n+1)$

如果数组B从1开始计数,那么对上述公式加1即可

按列优先

和按行优先存储的上三角矩阵压缩的推导几乎一样,可以先参考该节

$j$	第$j$列需要进入数组B的元素个数
1	$n$
2	$n-1$
$3$	$n-2$
…	…
$j-1$	$n-(j-2)$
$i$	$b_i⩽n-(i-1)$

$s_{j-1}$=$\frac{1}{2}(n+(n-(j-2)))(j-1)$=$\frac{1}{2}(2n-j+2)(j-1)$

第$j$列需要入数组的元素数量为$b_j=i-j+1$,(由于是下三角,$i⩾j$)

$k$=$s_{j-1}+(i-j)$=$\frac{1}{2}(2n-j+2)(j-1)+(i-j)$,B[0...n(n+1)/2]

$k$=$\frac{1}{2}(2n-j+2)(j-1)+(i-j)+1$,B[1...n(n+1)/2+1]

上三角矩阵

分别讨论按行优先和按列优先存储下,$i,j,k$的关系

按行优先

$i$	第$i$行需要进入数组B的元素个数$b_i$(行$i$上属于上三角的元素的个数)
1	$n$
2	$n-1$
$3$	$n-2$
…	…
$i-1$	$n-(i-2)$
$i$	$b_i⩽n-(i-1)$

上面的表格中,第$i$行实际上不一定填满,利用第$i$行的公式,带入$i-1$得出第$i-1$行需要入B数组的元素个数:$n-i+2$

累计前$i-1$行的元素的入数组B的元素个数(为了讨论方便,后续省略入数组B这几个字,直接用元素数量称呼),这是个等差数列求和问题,$s_{i-1}$=$\frac{1}{2}(n+(n-i+2))(i-1)$=$\frac{1}{2}(i-1)(2n-i+2)$,利用的求和公式中没有公差的$s_n=\frac{1}{2}(a_1+a_n)n$(注意这里项数$n=i-1$,对应的是求和前$i-1$行的元素数量)

然后单独计算第$i$行的元素数量,这时候$b_i=j-i+1$,第$i$行中$a_{ij}$前面的元素为$j-i$;

因此$a_{ij}$存入数组B[0...n(n+1)/2]后的索引为

• $k$=$s_{i-1}+b_i-1$=$\frac{1}{2}(i-1)(2n-i+2)+(j-i)$,$(i⩽j)$ 主对角线和上三角区域

• $k=\frac{n(n+1)}{2}$,$(j<i)$,下三角区域

使用条件大括号描述
$$k_0(i,j)=\{\begin{array}{l}\frac{(i-1)(2n-i+2)}{2}+j-i;(i⩽j)\\ \frac{n(n+1)}{2};(j<i)\end{array}$$

下三角区域的元素取值都一样,因此总是将值存放到同一个位置,这个位置一般设置在数组B的最后一个位置(数组的长度为$\frac{n(n+1)}{2}+1$,数组B从0开始计数(B[0...n(n+1)/2],那么最后一个元素的索引就是$\frac{n(n+1)}{2}$

如果是存入B[1...n(n+1)/2+1],公式会发生变换

• $k_1=S_{i-1}+s_i$=$\frac{1}{2}(i-1)(2n-i+2)+(j-i+1)$,$(i⩽j)$

• $k_1$=$\frac{n(n+1)}{2}+1$,$(j<i)$

按列优先

案列优先存储上三角矩阵的上三角部分和对角线元素,推导过程和按行存储类似

$j$	第$j$列需要进入数组B的元素个数
1	$1$
2	$2$
$3$	$3$
…	…
$j-1$	$j-1$
$j$	$⩽j$

先计算前$j-1$列需要压缩的元素数量,$s_{j-1}$=$\frac{1}{2}(1+(j-1))(j-1)$=$\frac{1}{2}j(j-1)$

第$j$列的元素数量为$i$;

所以$k(i,j)$=$\frac{1}{2}j(j-1)+i-1$,(B[0...n(n+1)/2])

若存入B[1...n(n+1)/2+1],则$k(i,j)$=$\frac{1}{2}j(j-1)+i$

A[0...][0...] vs A[1...][1...]

• 前面的公式都是在$i\in [1,n],j\in [1,n]$情况下推导的
• 有时矩阵的坐标是从0开始的:$i\in [0,n],j\in [0,n]$
  • 如果矩阵是A[0...][0...],第一个元素是$a_{00}$,那么相关公式不能直接使用
  • 幸运的是,这个调整比较简单,只需要将$i,j$直接映射$i+1,j+1$就可以了