讲解在线视频

本节，我们来学习特殊矩阵的压缩存储

在实际应用当中

很多矩阵，它们的值分布是有一定规律的

为了节省内存

我们没必要存放矩阵当中所有元素的值

我们只存放其中一部分

这就叫做压缩存储

在压缩存储之后，我们要能还原回之前想表示的这个矩阵

现在，我们来看第一类特殊矩阵，对称矩阵

对称矩阵，元素是沿着主对角线对称的

比如，这两个5

这两个17，等等

换句话说

矩阵中的aij元素，是等于aji的

很明显

我们没有必要存放下矩阵中全部的n^2个元素

而是只存储主对角线，及其一侧的值，就可以了

比如，我们只存图中绿色的区域

也就是矩阵的下三角部分

当然，你存上三角，也是可以的

好，现在，我们用一个一维数组A

并且以行为主序，来存放绿色区域的元素

比如，第0行，存放1个元素，10

因为这里的i、j，都是下标

都是从0开始的

所以，我们使用了第0行这种称法

这个希望大家要注意

好，下一行，也就是第1行，存放2个元素，5、7

第2行，存放3个元素，3、12、20

第3行，存放最后的4个元素

现在，我们一般化

对于n阶的对称矩阵，一共要存多少个元素呢

换句话说

数组A的长度是多少呢

通过刚才的分析

我们能明显看出

在绿色区域中，每一行的元素个数

其实与行号是存在某种联系的

比如，右边这个表格，列出了每一行存放的元素个数

与该行的行号之间的关系

第0行，存了1个

第1行，存了2个

第i行，应该是i+1个

最后一行(也就是第n-1行)，存了n个

所以，存放的元素总个数，就是1累加到n

也就是n(n+1)/2

对于这样一个数组A

我们如何根据任意给定的下标i、j，找到对应的元素aij呢

毕竟，你压缩存储了之后，你还要能还原回压缩前的矩阵啊

我们来分析一下i、j的大小关系

先看当i>=j的时候

i>=j，元素应该是落在绿色区域内的

原因很简单

因为主对角线上，元素的i、j下标是相等的

现在i>=j，说明aij是出现在矩阵的下三角位置的

也就是绿色的区域

现在，aij在绿色的区域

而绿色区域的元素，我们是存了的

于是，我们就应该在数组A中，去找aij

现在问题是，aij到底在A中的哪个下标位置呢

很简单

我们就看aij前面，一共存了多少个元素，就行了

还是看右边这个表格

aij所在的行

它上面，一共有i行

别忘了，i、j都是从0开始的

也就是，行号从0到i-1的这一共i行

这i行一共有多少个元素呢

就是1累加到i，也就是这里的这一项

哎

然后，在aij本行

位于它前面的元素，一共有j个

所以，j跟刚才红色框框住的相加

就是aij元素在A中的下标了

我们再来看另一种情况

当i

i

这时候，aij应该是位于绿色区域之外的

但绿色区域之外的元素

我们根本就没存

那怎么找到aij的值呢

别忘了，我们现在压缩存储的是对称矩阵，aij虽然没存

但我们存了aji，aji不就在绿色区域里面吗

所以，这时候，我们只需要交换一下上面这个下标中的i和j

就得到了aij在A中的下标了

这是对称矩阵

我们再来看第二类特殊矩阵，上/下三角矩阵

这里，我们以下三角矩阵为例

下三角矩阵

那些位于主对角线一侧的元素

都是某一个常数c

比如这个图

这个常数c啊，通常是0

但也有可能是其他非0的值

对于这样的矩阵

我们也没必要存放所有的n^2个元素

而是跟刚才的对称矩阵类似

只存放主对角线及其一侧的值，以及这个常数c，就可以了

同样，我们用一维数组A来做压缩存储，也是按行为主序来存放

那么，数组A这时候的长度是多少呢

很简单，就比刚才讲的对称矩阵多了这个单元

因为多存了一个常数c

前面的多个单元，跟刚才的对称矩阵都是一样的

都是一个下三角矩阵

所以，这时候的A

它的长度就是之前的对称矩阵的长度，再加上一个1

也就是这个

那么，我们怎么去找到给定的i、j下标对应的aij元素呢

跟刚才一样

就是看aij是不是落在我们存的那个下三角区域里面

如果在

也就是当i>=j的时候

我们就直接在数组A中找

这时候，aij所在的下标，跟之前的对称矩阵是一模一样的

因为A这个数组，它前面的那些单元

也就是除了最后一个元素之外的那些单元

跟对称矩阵是完全一致的

所以，这时候，aij就在这个下标位置

另外一种情况，i

很明显

这时候，aij就不在下三角位置了

不在下三角，那就在上三角

上三角里面都是常数c

所以，这时候aij的值，就是常数c

C

但是常数c从哪里才能找到呢

不就是A的最后一个下标n(n+1)/2，这个位置吗

接下来，我们来看最后一类特殊矩阵，对角矩阵

对角矩阵中的非零元素，仅出现在以主对角线为中心的带状区域

而其余位置的元素都是0

所以，对角矩阵有时也称为带状矩阵

比如这个图，绿色区域

实际上是由3条对角线组成的

故称为5阶的三对角矩阵

因为，主对角线左右两侧的对角线条数都是一样的

所以，带状区域中的对角线总条数k，一定是一个奇数

比如这里的3

既然只有带状区域中的元素分布没有规律

因此，我们就只存储该带状区域的元素，就可以了

存的时候

我们依然是按矩阵的行为主序来存

大家看这里的一维数组A

第0行，存2个；第1行，存3个；第2行，存3个

一直往后

最后一行，又回到了2个

那么，这样一个一维数组，总共要存多少个元素呢

为了方便计算

我们可以这样看

红色的主对角线上，是有n个元素的

紧挨其左侧的蓝色对角线上，有n-1个元素

现在，假设k是5

也就是说

如果蓝色对角线的左侧还有一条对角线

那么，这条对角线上的元素个数，将继续以1递减

右侧也是类似的

因此，带状区域上的非零元个数

一定是关于矩阵阶数n和对角线条数k的某个函数

这里由于时间关系

我们就直接给出来了，是这个

具体的推导过程，我们将在本节课程的讨论中详细给出

当然，同学们也可以尝试着自己推导一下

其实也比较简单

对于我们这里给出的对角矩阵

n=5，k=3

那就是3*5-(9-1)/4，等于13

也就是说

一维数组A的长度就是13

它们的下标

就是0到12

有了一维数组A之后

我们要解决的问题仍然是，如何根据A还原回压缩存储前的对角矩阵

也就是说

给定任意i、j下标，如何确定aij的值

通过分析，我们不难发现

当i、j之差的绝对值超过了(k-1)/2的时候

aij应该是位于带状区域之外的

为什么是这样呢，我们这样看

最左侧的对角线，也就是那条蓝色的对角线

它上面的元素，i下标减去j下标的值

都是等于(k-1)/2，也就是1

比如这里的21、34

也就是说，如果i>j

并且i-j比(k-1)/2还要大

那，aij就位于最左侧对角线的左下区域(这一部分)

它们都是0

与之对称的，如果i

并且i-j比-(k-1)/2还要小

这时候，aij就位于最右侧对角线的右上区域，它们也是0

所以，我们综合这两种情况

当i减j的绝对值超过了(k-1)/2的时候

也就是这个条件，这时候，aij的值就是0

比如，这里的a31，还有a04等等

它们都是满足这个条件的

所以，元素的值都是0

那另外的情况呢

当|i-j|<=(k-1)/2的时候(这个条件)

那aij又是多少呢

这时候，我们很难像前面的两种特殊矩阵那样，算出一个通项公式

因为这时候，aij在数组A中的下标

实际上取决于i、j、n、k它们的具体值

我们只能根据它们的具体值来计算

待会我们会看到

比如，我们现在要去找a32，a32应该是它

(注意)i、j都是从0开始

容易知道，a32所在行的上面，实际上存了3行

这3行分别有2、3、3个元素

再看a32所在的那一行

它前面存了多少个元素呢

我们刚才分析过了

对于a32，它的i下标减去j下标，也就是3-2，等于1

说明，a32就位于最左侧的对角线上

因为这时候，(k-1)/2就是1

它就是该行存的第一个元素

所以，在a32前面，没有存其他的任何元素

它在A中的下标就是2+3+3，就是A[8]

对应的值，就是这里的21

我们再换一个元素，比如a34，在这儿

也是类似的，只不过这时候

它的i下标减去j下标，3-4，等于-1

也就是-(k-1)/2

说明a34就位于最右侧的对角线上

它是该行的第3个元素

换句话说

在这一行，a34前面，一共存了两个元素

所以，a34在A中的下标就是2+3+3，再加一个2

这个2+3+3，跟刚才的a32是一样的

都是它上面的3行存放的元素

这里的加2，是表示在a34那一行，a34前面存了两个元素

所以就是A[10]，对应的值就是-6

好，这是对角矩阵