特别矩阵与稀疏的压缩存储和算法实现

本文格式为Word版，下载可任意编辑——特别矩阵与稀疏的压缩存储和算法实现

特别矩阵与稀疏的压缩存储和算法实现1998年论文

维普资讯

第15卷1998年

第3期8月

贵州大学学报(自然科学版)JunlluhuUnvri(arlcec)ora0GioisyNtaSinezetu—

、

1No,5.Au19g.98

—

0—

特别矩阵与稀疏的压缩存储和算法实现mH十^摘要

.

下；’(6Ⅷ㈣)f。、1ff/f、f

本丈结合《学结构*中遇到教学问题，就对称矩阵、三角矩阵、三对角教

矩阵、稀疏矩阵的压缩储进行了计论，并给出了建立这些存付的类psa算法描述.acl

苎.中分图g竺类-

Tt3.1111

、塑三三丝苎’

稀矩、组疏障数

奄.‘留存罐矩阵的运算在计算机中一般用二维组来实现.将矩阵存放到~维的线性存储空问中，一般有两种存储方式：一种以行序为主的存储方式，即先存放第一行，接着存放的其次行…直

到第N行；另一种以列序为主的存储方式，即先存放第一列，接着存放其次列…直接到第N行.对于普通矩阵的这种存储结构的读与写运算，用高级语言来实现已趋于成熟，这里不再探讨.

在现实问题经常会遇到阶数很高并且矩阵中有大量值一致的元素或零元素，若依旧按行或列的顺序存储每一个元素，会浪费大量的存储空问，以对这一种矩阵应采取压缩存储.所对压缩存储的矩阵的读、写与对非压缩储存矩阵的读、写有所不同.下面分别探讨它们

l对称矩阵n阶列称矩阵元素按主对角线对称一致，一般满足以下性质：

a一a

其中

1一i一n,j

对于对称矩阵，可以为每一对对称元素(值一致)分派一个存储空问.为此只存储矩阵的下三角形部分或上三角部分.只存储下三角形，则存储元素为：1IIaI

a:

自22

1…an1aIan3…a邶

总共存储元素的个数为：1+3++2+4收精日期：19一(8一29{

特别矩阵与稀疏的压缩存储和算法实现1998年论文

维普资讯

整塑

垩！壁堕堑睦煎煎的压缩存储和算法实现

.1.27(

这样可将n个

元素的压缩存储到n*(412存储空间中.假设以数组M[,?n-l/个1.

1el作为N阶X称矩阵的存储结构-按行优先存储，则矩阵元素a与之在一维数组中的位l/,J置P(]即用于存储tl有如下对应关系：mli~

J(l/Tl一12Jl*(-1/Jj)2+i

当l=J当ji,

当访问N阶刈对矩阵中的任一元素aN需按上述公式计算出P.,只i一一

访问m矩阵中的m

L]就行T-建立一个N阶矩阵的压缩存储算法如下：ppedbgneifri1t(o一onIo

eVARM:aY[.n*(+12faaye;l(】n)/]otp)d

frj1tt0=Ontora()eda:

ii=jtefhnp=i(—1/i‘i)2

esleP:j(-1/ij)2

m[]=ap]

2三角矩阵N阶三角矩阵可划分为如下两种

Il_f.la

围()b

是图()称为上三角矩阵，除常量C之外，其余元素分布在主对角线及以上，特点是a一

i:图()称为下三角矩阵，除常量C之外其余元素他布在主对角线及以下，特点是;b

i=j.

~

阶下三角矩阵，可以将该N阶矩阵压缩存储到mI;(1+12])1+1维数组中.其存储形式为：..

a1I

Jn[]l2

alri]

_二l———=-

I!

m_(+1/-1m[(+1/]n(+1/+1门n)2]n门)2m[几)2]

该M矩阵的建立方法同前面探讨的对称矩阵压缩存储其下三角矩阵的方法类似、

,

不再赘

】-

r

位置

:+b考放三角矩阵，按行优n(1,则矩个储间设一数匕上存仍需先顺n)21存素，用维组：三磐的储然要*序存放/阵元

空l=阵_+++、

p之间有如下对应关系

.,

与之在。’

一…

的~

特别矩阵与稀疏的压缩存储和算法实现1998年论文

维普资讯

.

281.『*n

贵卅大学学报(l自然科学版)EJ

箜鲞塑

((-J)2i)

(ni2)+ji12+—+

J:i

当ij,,均为c时l】.,故存放在mn(一12]下标变量中.n)/+1当i=i时i与P的刈应关系较为繁杂t推导如下：、j

上三角矩阵|,第一行有n】1}J一+个元索；其次行有n+1元素；……第n行有n一2个n1元索，由此类推，第t应有n+1元素.元素a之前共有-1,这i1共有+个行—i个一行行(一1_)一(一21+…+((—1_)个元素.根据数学公工可得导出上式之和n_】n+)n1)_1为：

(一12’i)/

(一11一a—nnl

lO

O……………O

O

a1a一

从上面的形式可导出，非零元素的下标变化规律为：当i1i】2当1时、j;=n时J一1=n、n当1n时j一1、i1i=i、i+

将这三条刈角线上的非零元素存储到一个维数组中，依旧按行先顺序.可得到如下存储序列：_l1la12z1.:If:lxal::ajl…In—I-2ln

a…

i一

.

a一

1

al1n

将它们存储到M数组中t则该一维数组共有3(一2t43一2元素.非零元素an)-;n个-在M数组中的位置推导如下

a之前共有i1,共有3(一1一1非寒元素，第i,在非零元索a之前还有〞一行i)个行i}

特别矩阵与稀疏的压缩存储和算法实现1998年论文

维普资讯

第3期(一】(1

刘

平：特别矩阵与稀疏的压缩存储和蔓法塞理

:

:

1)个非零元素，所以a在M数组中的位置为P为：)P一2。(1一J1)I1一j12;In=.—ji—1=1tn

建立三对角矩阵的压缩存储矩阵M[:3(一1+2的算法如下1n)3poeuecet3(Em:ary13*(—1_2faaye;rcdrraeVIl-ran)_3ottp)dbengi

fri1too一02d

[d()raa;

p=2*(1一JI1:=a:I);F)I[]]e,f—n-e“]eLsiIil

fr1一no:11oond

Eed({P一2*(1ra)1】+jE]一a;mp]2*(1一J1[]一aedi);1p1]n

4稀疏矩阵稀疏矩阵是指该矩阵中非零元素远远小于矩阵元素的个数，而非零元素的排布又没有规律，则称矩阵为稀疏矩阵.然在存储一个高阶的稀疏矩阵时，只有必要储其非零元素.我们依旧将稀疏矩阵中的非零元素压缩存储到一个一维数组，但由于非零元素分布不规则一此时还应记住非零元素的行、列位置IJ与，为此这个一维数组的每个元索不

再是简单数据，而应当是一个记录数据，形式如下：

元素值所有非零元素的数组就构成j一个记录数组.如以下的稀疏矩阵，l001000

1300000A=l一102000

100l0040O03000

可将其非零元素存储到如下的一个记录数组sp中：

特别矩阵与稀疏的压缩存储和算法实现1998年论文

维普资讯

20261

贵州大学学报(然科学版)自13

第1耋塑5s[]p】s[]p2s[]p3s[3p4s[]p5s[3p6

1

圈345

I263

一124—3

对sP数组的类型定义及建立一个稀疏矩阵的算法如下constteypmax;k;node—rcdeor、

iner:itge;

num:dttp;ed;aayen

smarxra[ma]ooepti=ary1xfd;npoeuetets(apsmarx;rcdrrapvrspti)bgicunt一eno0:

fornu一1omaxdto

[ed(,j)on=cut;raj,x;cuton+1

s[on3.=p[on3jjpcut..;scut.~;s[on]nm.=x;n;pcu,.u.]ed

ThcdMeoyoeilmarxaePakemrfSpca—tindSpaemarxc—tiatlothmecrptonndisAgriDsii

LiPigun('peneeGuzou.Guyn50)kmutrCetr0ih￣[as5025

AbtatIhsatce,wedsustepceesrcntirilicshakdmmorfseilmarxadsaemarxyopca—tinpc—ti

’

.

Wemetihrcsftahnnieilo