5.2 矩阵的压缩存储在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节课我们讨论矩阵的压缩存储

矩阵是我们熟悉的一种数学对象

在科学和工程的计算问题当中

矩阵都是一种常用的工具

我们编制程序实现矩阵的时候

简单而又自然的方法，就是将矩阵描述为一个二维数组

或者说利用一个二维数组，来实现矩阵的存储，运算

利用二维数组实现矩阵的存储，可以对元素进行随机存取

并且各种矩阵的运算也非常简单

但是在矩阵的实际应用当中，很多矩阵的维数是非常高的

用二维数组存储空间占用很大

另外，有一些特殊的矩阵，它的数据分布呈现一定的规律性

针对这种矩阵。我们可以考虑进行压缩存储

通过压缩存储可以极大的降低矩阵存储空间的需求

我们主要讨论针对特殊矩阵的压缩存储

特殊矩阵是非零元素呈某种规律分布的矩阵

比如说对称矩阵，从图中可以看出

对称矩阵的元素有特殊性，沿主对角线

对称的元素的值是相等的

就是矩阵第i行第j列的元素值等于第j行第i列的元素

如示例中，第1行第4列的元素值是7

第4行第1列的元素值也是7

二者相等，其它矩阵中的元素也有这样的性质

另一个例子是下三角矩阵

下三角矩阵，主对角线以上的元素是一个常量c

很明显，采用二维数组存储的话

常量c会被重复存储很多次

针对这样的特殊矩阵，可以考虑采用压缩存储

压缩存储的基本原则是：为多个相同的非零元素

只分配一个存储空间

而对零元素，不分配存储空间

我们用下三角矩阵的例子来看一下

如图中的下三角矩阵，可以考虑只存储下三角

也就是红三角框框起来的这一部分，上三角的元素

因为都是一个常量c，只需要存储一份就可以了

当然就不用二维数组了

比如说我们采用这样的存储方式

利用一个一维数组sa来实现下三角矩阵的压缩存储

下三角任然是一个二维结构，而sa是一个一维数组

和数组的存储类似

需要把下三角的二维结构转换为一个一维序列

才能在sa中存储

我们采用行序的办法

就是先存第1行的3，随后存第2行的6和2

再存第3行，这样一直存储到最后一行

示例的下三角中总共有15个元素

存储到数组0~14号，这15个单元中

上三角就只存一个常量c，我们把它存在第15号单元

利用这样的方式，实现了下三角矩阵的压缩存储

如果用二维数组来存示例中的矩阵，需要25个单元

压缩存储以后，只需要16个单元

当然，这样的存储也带来了一个问题

矩阵本身的逻辑结构是一个二维的结构

当我们使用矩阵参与运算的时候

如果要使用矩阵元素aij

就必须解决一个问题，压缩存储以后

矩阵元素aij，存储到了数组空间的哪一个下标单元k了

如示例中，矩阵第4行第1列的元素是7

该元素存在sa的6号单元

那么，当需要存取矩阵中该元素时

要到sa的6号下标单元去存取

下面我们通过几个特殊矩阵的例子来重点讨论一下这个问题

首先看一下对称矩阵

前面我们已经通过例子看到，对称矩阵中

aij和aji是相等的

那么，我们可以为这两个对称元素只分配一个存储单元

让两个对称的元素共享一个存储空间

所以呢，只需要存储矩阵中上三角或下三角的元素

假设我们存储下三角

对于一个n乘n的矩阵

存储下三角需要n(n+1)/2个存储单元

仍然用一个数组sa来实现存储，采用按行存的方式

先存第1行a11，随后存第2行的a21，a22

这样一行一行的存下来，最后一个存储第n行

如果矩阵计算的过程当中

需要存取上三角的元素的时候

我们就把它映射到下三角的对称元中去

当然这样存了以后，就遇到了我们前面讨论的那个问题

必须在矩阵的元素aij和它在sa的存储位置k之间

找到一个对应关系。下面我们看一下怎么做

这种情况和数组存储的情况有些类似

方法也是类似的。核心是计算在按行存储的方式下

下三角中的aij前面存了多少个矩阵元素

观察一下图，第i行前面，总共存了i-1行

其中，第1行有一个元素，第二行有两个元素

第i-1行有i-1个元素

从红色的框线中，我们可以看到

下三角的元素构成了一个梯形

梯形的上底是1，下底是i-1，高也是i-1

梯形当中元素的个数

可以采用求梯形面积的办法来计算

也就是(1+( i-1))( i-1)/2

计算结果是前i-1行的总个数

aij在第i行当中是第j个

所以在前i-1行总个数的基础上再加一个j

考虑到sa中存储是从0号单元开始，再减一个1

通过这个公式，就可以计算出矩阵下三角中当中aij这个元素

在sa中的存储位置k

化简一下，当i大于等于j时

也就是所存取的元素是下三角中的元素的时候

它在sa中的位置k，可以用i(i-1)/2+j-1来计算

存取上三角当中元素的时候，也就是i

我们知道上三角中aij的对称元是下三角中的aji

我们可以用公式j(j-1)/2+i-1来计算它对称元的位置

然后进行存取

对称矩阵的压缩存储我们就介绍到这儿

下面我们看一下三角矩阵

三角矩阵有上三角和下三角两两种

上三角矩阵的下三角，不包括主对角线

他的元素均为常数

下三角矩阵正好相反

我们以下三角矩阵为例

前面已经看过一个示例

首先存储矩阵的下三角部分

存储方式和对称矩阵相同

下三角矩阵需要多储存一个上三角中的常数c

把它存到n(n+1)/2号单元

存好以后，如果存取的是下三角的元素

计算公式和对称矩阵中是一样的

如果存取的是上三角的元素

那么所有的元素都对应到n(n+1)/2这个单元

下面我们看一下对角矩阵

对角矩阵是指所有的非零元素集中在

以主对角线为中心的带状区域中

其元素皆为零

我们以三对角矩阵为例来讨论一下这个问题

三对角矩阵从它的分布特点来看

就是非0元素集中在主对角线

以及和主对角线平行的上下两条对角线中

其余位置的元素皆为零

考虑按行存储，先存第一行a11，a12

随后存第二行，直到第n行，和前面类似的问题

要存取非0元aij的时候

应该到数组中哪个位置可以去找它？

三对角矩阵的非0元下标有这样的特点

j-i的绝对值小于等于1，考虑非0元aij

方法也和前面的特殊矩阵类似

要是计算aij前面存了多少个元素

它前面总共有i-1行，每行是三个元素

考虑到第1行就两个元素

用3*(i-1)-1计算前面i-1行的总个数

每行有3个元素，需要考虑aij是第i行第几个元素

用j-i+2来计算，比如说a 34

4-3+2=3，说明它是这行当中的第3个元素

考虑到从0号单元开始存储

我们可以用3*(i-1)-1加j-i+2再减1算出

应该到数组中哪个位置k去找aij

对角矩阵的另一种存储方式是按对角线存

相应的计算方法类似，同学们课后考虑一下

特殊矩阵的形式还有很多

但压缩存储的思想都差不太多

都可以采用类似的方法处理

好同学们，这节课我们就讨论到这

下次课再见