首页 > 代码库 > 特殊矩阵的压缩存储(转自chunlanse2014)

特殊矩阵的压缩存储(转自chunlanse2014)

 

 

对称矩阵

对于一个矩阵结构显然用一个二维数组来表示是非常恰当的,但在有些情况下,比如常见的一些特殊矩阵,如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等,从节约存储空间的角度考虑,这种存储是不太合适的。下面从这一角度来考虑这些特殊矩阵的存储方法。

对称矩阵的特点是:在一个n 阶方阵中,有aij=aji ,其中1≤i , j≤n,如图5.5 所示是一个5阶对称矩阵。对称矩阵关于主对角线对称,因此只需存储上三角或下三角部分即可,比如,我们只存储下三角中的元素aij,其特点是j≤i 且1≤i≤n,对于上三角中的元素aij ,它和对应的aji 相等,因此当访问的元素在上三角时,直接去访问和它对应的下三角元素即可,这样,原来需要n*n 个存储单元,现在只需要n(n+1)/2 个存储单元了,节约了n(n-1)/2个存储单元,当n 较大时,这是可观的一部分存储资源。


如何只存储下三角部分呢?对下三角部分以行为主序顺序存储到一个向量中去,在下三角中共有n*(n+1)/2 个元素,因此,不失一般性,设存储到向量SA[n(n+1)/2]中,存储顺序可用图5.6 示意,这样,原矩阵下三角中的某一个元素aij 则具体对应一个sak,下面的问题是要找到k 与i、j 之间的关系。

技术分享

对于下三角中的元素aij,其特点是:i≥j 且1≤i≤n,存储到SA 中后,根据存储原则,它前面有i-1行,共有1+2+…+i-1=i*(i-1)/2 个元素,而aij 又是它所在的行中的第j 个,所以在上面的排列顺序中,aij 是第i*(i-1)/2+j 个元素,因此它在SA 中的下标k 与i、j 的关系为:
k=i*(i-1)/2+j-1 (0≤k<n*(n+1)/2 )


若i<j,则aij 是上三角中的元素,因为aij=aji ,这样,访问上三角中的元素aij 时则去访问和它对应的下三角中的aji 即可,因此将上式中的行列下标交换就是上三角中的元素在SA 中的对应关系:
k=j*(j-1)/2+i-1 (0≤k<n*(n+1)/2 )

综上所述,对于对称矩阵中的任意元素aij,若令I=max(i,j),J=min(i,j),则将上面两个式子综合起来得到: k=I*(I-1)/2+J-1。

 

三角矩阵

形如图5.7 的矩阵称为三角矩阵,其中c 为某个常数。其中5.7(a)为下三角矩阵:主队角线以上均为同一个常数;(b)为上三角矩阵,主队角线以下均为同一个常数;下面讨论它们的压缩存储方法。

1. 下三角矩阵


与对称矩阵类似,不同之处在于存完下三角中的元素之后,紧接着存储对角线上方的常量,因为是同一个常数,所以存一个即可,这样一共存储了n*(n+1)+1 个元素,设存入向量:SA[n*(n+1)+1]中,这种的存储方式可节约n*(n-1)-1 个存储单元,sak 与aji 的对应关系为:

技术分享

2. 上三角矩阵

 

对于上三角矩阵,存储思想与下三角类似,以行为主序顺序存储上三角部分,最后存储对角线下方的常量。对于第1 行,存储n 个元素,第2 行存储n-1 个元素,…,第p 行存储(n-p+1)个元素,aij 的前面有i-1 行,共存储:

个元素,而aij 是它所在的行中要存储的第(j-i+1)个;所以,它是上三角存储顺序中的第(i-1)*(2n-i+2)/2+(j-i+1)个,因此它在SA中的下标为:k=(i-1)*(2n-i+2)/2+j-i。综上, sak 与aji 的对应关系为:

技术分享
 

带状矩阵

n 阶矩阵A 称为带状矩阵,如果存在最小正数m ,满足当∣i-j∣≥m 时,aij =0,这时称w=2n-1 为矩阵A 的带宽。如图5.10(a)是一个w=3(m=2)的带状矩阵。带状矩阵也称为对角矩阵。由图5.10(a)可看出,在这种矩阵中,所有非零元素都集中在以主对角线为中心的带状区域中,即除了主对角线和它的上下方若干条对角线的元素外,所有其他元素都为零(或同一个常数c)。

带状矩阵A 也可以采用压缩存储。

一种压缩方法是将A 压缩到一个n 行w 列的二维数组B 中,如图5.10(b)所示,当某行非零元素的个数小于带宽w 时,先存放非零元素后补零。那么aij 映射为b i′j′,映射关系为:

另一种压缩方法是将带状矩阵压缩到向量C 中去,按以行为主序,顺序的存储其非零元素,如图5.10(c)所示,按其压缩规律,找到相应的映象函数。如当w=3 时,映象函数为:k=2*i+j-3

特殊矩阵的压缩存储(转自chunlanse2014)