计算机考研稀疏矩阵优秀PPT.ppt

《计算机考研稀疏矩阵优秀PPT.ppt》由会员分享，可在线阅读，更多相关《计算机考研稀疏矩阵优秀PPT.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机考研稀疏矩阵现在学习的是第1页，共26页5.3.1 特殊矩阵bb对称矩阵对称矩阵对称矩阵对称矩阵:a aijij=a=ajiji(1=i,j=n)(1=i,j=n)bb下三角矩阵下三角矩阵下三角矩阵下三角矩阵:当当ijij时时,aij=0,(1=i,j=n)aij=0,(1=i,j 1|i-j|1时时,a aijij=0,(1=i,j=n)=0,(1=i,j=n)a a1111 a1212 a1313.a1n1n a2121 a a2222 a2323.a2n2n a3131 a3232 a a3333.a3n3n .an1n1 an2n2 an3n3.a annnnAnxn=现在学习的

2、是第2页，共26页对对 称称 矩矩 阵阵:aij=aji(1=i,j=ji=jbb k=k=k=k=bb j(j-1)/2+i j(j-1)/2+i j(j-1)/2+i j(j-1)/2+i 当当 i ji j现在学习的是第3页，共26页例5.3 对称矩阵bbn=5,1+2+3+4+5=5*(5+1)/2=15n=5,1+2+3+4+5=5*(5+1)/2=15bb一维数组SA1.15作为数组作为数组A的存储结构:bbSA=(4 4 4 4 5 2 2 3 1 3 3 2 5 2 8 8 1 6 7 9 5 5 5 5)bb如:a5,3=a3,5=7bb k=5(5-1)/2+3=13 k=

3、5(5-1)/2+3=13bb故故:sa13=7 4 4 5 3 2 15 2 2 1 5 63 1 3 3 2 72 5 2 8 8 91 6 7 9 5 5A=4 4 5 2 2 03 1 3 3 2 5 2 8 8 1 6 7 9 5 5A=现在学习的是第4页，共26页下下三三角角矩矩阵阵:当ij时,aij=0,(1=i,j=j)bb 0 (0 (当当 i j)i 1|i-j|1时时,aijij=0,(1=i,j=n)=0,(1=i,j=n)bb a a a a11111111 a12121212 0 0.0 0 0.0bb a2121 a a22222222 a a2323 0 .0b

4、bAnxn=0 a3232 a a3333 a a34343434 .0bb .bb 0 0 0.a 0 0 0.ann-1nn-1 a annnnnnnnbb一一维维数数组组SA1.3*n-2作为数组A下三角元素的存储结构:bbSAk=SAk=a a a a11111111,a,a12121212,a,a21212121,a a a a22222222,a,a23232323,a,a32323232,a a a a33333333,a,a34343434,.,a,.,ann-1nn-1nn-1nn-1,a a a annnnnnnn bb k =1 2 3 4 5 6 7 8 3n-3 3n

5、-2k =1 2 3 4 5 6 7 8 3n-3 3n-2现在学习的是第7页，共26页bbsaksak和和ai,jai,j的一一对应关系的一一对应关系:bb sak,k=3*(i-1)+j-i+1,sak,k=3*(i-1)+j-i+1,sak,k=3*(i-1)+j-i+1,sak,k=3*(i-1)+j-i+1,bbai,j=ai,j=ai,j=ai,j=当当|i-j|=1|i-j|1|i-j|1现在学习的是第8页，共26页例5.5 三对角矩阵bb 4 4 4 4 3 3 3 3 0 0 0 bb 5 2 2 5 2 2 0 0bb A=0 1 0 4 1 0 4 1 0 4 1 0 4

6、 0 bb 0 0 2 8 72 8 72 8 72 8 7bb 0 0 0 0 0 0 9 5 9 5 9 5 9 5bb一维数组SA1.3*5-2作为数组A的的存存储储结结构构:SA=(SA=(4 4 4 4 3 5 3 5 2 2 2 2 2 1 2 1 0 0 0 0 4 2 4 2 8 8 7 9 5 5 5 5)bb如如:a5,4=9 a5,4=9bb k=3*(5-1)+4-5+1=12bb故故故故:sa12=9sa12=9现在学习的是第9页，共26页5.3.2 5.3.2 稀疏矩阵 通常稀疏因子稀疏因子0.05时称为稀疏矩阵.bb例例5.6 5.6 bb 0 12 9 0 0

7、0 0 0 0-3 0 0 15 0 12 9 0 0 0 0 0 0-3 0 0 15bb 0 0 0 0 0 0 0 12 0 0 0 18 0 0 0 0 0 0 0 0 12 0 0 0 18 0bbM=-3 0 0 0 0 14 0 9 0 0 24 0 0M=-3 0 0 0 0 14 0 9 0 0 24 0 0bb 0 0 24 0 0 0 0 T=0 0 0 0 0-7 0 0 24 0 0 0 0 T=0 0 0 0 0-7bb 0 18 0 0 0 0 0 0 0 0 0 0 0 0 18 0 0 0 0 0 0 0 0 0 0 0bb 15 0 0-7 0 0 0 0

8、0 14 0 0 0 15 0 0-7 0 0 0 0 0 14 0 0 0bb 0 0 0 0 0 0 0 0 0 0 0 0bbM:mu x nu(6x7)M:mu x nu(6x7)bbT:nu x mu(7x6)T:nu x mu(7x6)bbM M是是T T的转置的转置现在学习的是第10页，共26页稀 疏 矩 阵 的 存 储 结 构 一.三元组顺序表bb M:i j e T:i j eM:i j e T:i j ebb 1 2 12 1 3 -3 1 2 12 1 3 -3 bb 1 3 9 1 6 15 1 3 9 1 6 15 bb 3 1 -3 2 1 12 3 1 -3 2

9、1 12 bb 3 6 14 2 5 18 3 6 14 2 5 18 bb 4 3 24 3 1 9 4 3 24 3 1 9 bb 5 2 18 3 4 24 5 2 18 3 4 24 bb 6 1 15 4 6 -7 6 1 15 4 6 -7 bb 6 4 -7 6 3 14 6 4 -7 6 3 14 现在学习的是第11页，共26页三元组顺序表结构定义bb#define#define#define#define MAXSIZE 12500bbtypedef struct bb int i,j;bb Elemtype e;bbTriple;Triple;bbtypedef union

10、 typedef union bb Triple dataMAXSIZE+1;Triple dataMAXSIZE+1;bb int mu,nu,tu;int mu,nu,tu;bbTSMatrix;TSMatrix;bbTSMatrix M,T;M.datap .i .j .e012.maxsize现在学习的是第12页，共26页求 稀 疏 矩 阵 M的 转 置 矩 阵 TTSMatrix M,T;012345678012345678M.datap .i .j .eT.dataq .i .j .e现在学习的是第13页，共26页求稀疏矩阵M的转置矩阵TbbStatus TransposeSMat

11、rix(TSMatrix M,TSMatrix&T)Status TransposeSMatrix(TSMatrix M,TSMatrix&T)bb T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;bb if(T.tu)if(T.tu)bb q=1;q=1;bb for(col=1;col=M.nu;+col)for(col=1;col=M.nu;+col)bb for(p=1;p=M.tu;+p)for(p=1;p=M.tu;+p)bb if(M.datap.j=col)if(M.datap.j=col)bb T.dat

12、aq.i=M.datap.j;T.dataq.i=M.datap.j;bb T.dataq.j=M.datap.i;T.dataq.j=M.datap.i;bb T.dataq.e=M.datap.e;+q;T.dataq.e=M.datap.e;+q;bb bb bb retrun OK;retrun OK;bb/TransposeSMatrix/TransposeSMatrix现在学习的是第14页，共26页求稀疏矩阵转置的算法复杂度算法复杂度bb其算法复杂度是 O(nu*tu)O(nu*tu)O(nu*tu)O(nu*tu)bb而一般矩阵的转置算法的复杂度是O(mu*nu):O(mu*nu

13、):bb for(col=1;col=nu;+col)bb for(row=1;row=mu;+row)for(row=1;row=mu;+row)bb Tcolrow=Mrowcol;Tcolrow=Mrowcol;bb所以,当tu=mu*nu tu=mu*nu tu=mu*nu tu=mu*nu 时时,bb 算法复杂度是 O(nu*nu*mu)O(nu*nu*mu)O(nu*nu*mu)O(nu*nu*mu)bb 当当tu mu*nu tu mu*nu 时时,才适用现在学习的是第15页，共26页求 稀 疏 矩 阵M的 转 置 矩 阵T的快速方法bb为了减少算法复杂度为了减少算法复杂度,增加

14、两个向量 num num 和 cpot:cpot:bb numcol:M中第中第 col col 列中非零元素的个数;bbcpotcol:Mcpotcol:M中第colcol列中的第一个非零元素在T.data中中的位置的位置;bb有:cpot1=1;bb cpotcol=cpotcol-1+numcol-1bb 2=col=m.nu 2=col=m.nu现在学习的是第16页，共26页bb例例5.6 5.6 bb 0 12 9 0 0 0 0 0 0-3 0 0 15 0 12 9 0 0 0 0 0 0-3 0 0 15bb 0 0 0 0 0 0 0 12 0 0 0 18 0 0 0 0

15、0 0 0 0 12 0 0 0 18 0bbM=-3 0 0 0 0 14 0 9 0 0 24 0 0M=-3 0 0 0 0 14 0 9 0 0 24 0 0bb 0 0 24 0 0 0 0 T=0 0 0 0 0-7 0 0 24 0 0 0 0 T=0 0 0 0 0-7bb 0 18 0 0 0 0 0 0 0 0 0 0 0 0 18 0 0 0 0 0 0 0 0 0 0 0bb 15 0 0-7 0 0 0 0 0 14 0 0 0 15 0 0-7 0 0 0 0 0 14 0 0 0bb 0 0 0 0 0 0 0 0 0 0 0 0bb例5.65.6的向量的向量 n

16、um 和 cpot:bb col 1 2 3 4 5 6 7 bb num 2 2 2 1 0 1 0 num 2 2 2 1 0 1 0bb cpot 1 3 5 7 8 8 9现在学习的是第17页，共26页bbStatus FastTransposeSMatrix(TSMatrix M,TSMatrix&T)Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)bb T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;bb if(T.tu)if(T.tu)bb for(col=

17、1;col=M.nu;+col)numcol=0;for(col=1;col=M.nu;+col)numcol=0;bb for(t=1;t=M.tu;+t)+numM.datat.j;for(t=1;t=M.tu;+t)+numM.datat.j;bb cpot1=1;cpot1=1;bb for(col=2;col=M.nu;+col)for(col=2;col=M.nu;+col)bb cpotcol=cpotcol-1+numcol-1;cpotcol=cpotcol-1+numcol-1;bb for(p=1;p=M.tu;+p)for(p=1;p=M.tu;+p)bb col=M.

18、datap.j;q=cpotcol;col=M.datap.j;q=cpotcol;bb T.dataq.i=M.datap.j;T.dataq.i=M.datap.j;bb T.dataq.j=M.datap.i;T.dataq.j=M.datap.i;bb T.dataq.e=M.datap.e;+cpotcol;T.dataq.e=M.datap.e;+cpotcol;bb bb bb retrun OK;retrun OK;bb/FastTransposeSMatrix/FastTransposeSMatrix现在学习的是第18页，共26页 col 1 2 3 4 5 6 7 col

19、1 2 3 4 5 6 7 num 2 2 2 1 0 1 0 num 2 2 2 1 0 1 0 cpot 1 3 5 7 8 8 9 cpot 1 3 5 7 8 8 9012345678M.datap .i .j .e012345678T.dataq .i .j .e现在学习的是第19页，共26页求稀疏矩阵转置的快速算法的算法复杂度算法复杂度bb其算法复杂度是其算法复杂度是 O(nu+tu)O(nu+tu)bb 当当tu=mu*nu tu=mu*nu 时时,算法复杂度是算法复杂度是 O(nu*mu)O(nu*mu)bb 当当tu mu*nu tu mu*nu 时,时间复杂度将小得多时间复

20、杂度将小得多现在学习的是第20页，共26页bb#define MAXRC 100bbtypedef struct bb int i,j;bb Elemtype e;Elemtype e;bbTriple;Triple;bbtypedef struct typedef struct bb Triple dataMAXSIZE+1;Triple dataMAXSIZE+1;bb int rposMAXRC+1;int rposMAXRC+1;bb int mu,nu,tu;bbRLSMatrix;RLSMatrix;二.行 逻 辑 链 接 的 顺 序 表指出每一行的第一个非零元素在三元组中的位置M

21、.datap .i .j .e012.maxsizeM.rposrow现在学习的是第21页，共26页例5.7 矩阵的乘法 Q=M x N Q=M x N M:M:m m1 1 x n1 1 N:N:N:N:m m2 x n2 当当n1=m2 2时时 3 0 0 5 0 2 0 6M=0 -1 0 0 N=1 0 Q=-1 0 2 0 0 0 -2 4 0 4 0 0M.data N.data Q.data i j e i j e i j e 1 1 3 1 2 2 1 2 6 1 4 5 2 1 1 2 1 -1 2 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4 row 1 2

22、3M.rpos 1 3 4 row 1 2 3Q.rpos 1 2 3row 1 2 3 4N.rpos 1 2 3 5现在学习的是第22页，共26页求两个稀疏矩阵的乘积的算法bbQ初始化初始化;bbif(M和和N均是非零矩阵均是非零矩阵)bb for(arow=1;arow=M.mu;+arow)bb ctemp=0;ctemp=0;bb 计算计算Q Q中第中第arowarow行的积并存入ctempctemp中中;bb 将ctempctemp中非零元压缩存储到Q.data;Q.data;bb bb 现在学习的是第23页，共26页Status MultiSMatrix(RLSMatrix M,

23、RLSMatrix N,RLSMatrix&Q)if(M.nu!=N.mu)return ERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;/Q初始化;if(M.tu*N.tu!=0)/Q可能是非零矩阵 for(arow=1;arow=M.mu;+arow)ctemp=0;Q.rposarow=Q.tu +1；for(p=M.rposarow;pM.rposarow+1;+p)brow=M.datap.j;if(brow N.nu/*N.mu?*/)t=N.rposbrow+1;else t=N.tu+1;for(q=N.rposbrow;q t;+q)ccol=N.dataq

24、.j;ctempccol+=M.datap.e*N.dataq.e;/for p for(ccol=1;ccol MAXSIZE)return ERROR;Q.dataQ.tu=arow,ccol,ctempccol;/for arow /if return OK;现在学习的是第24页，共26页时间复杂度时间复杂度:ctemp 的时间复杂度是的时间复杂度是 O(M.mu X N.nu);O(M.mu X N.nu);bb求求Q所有非零元的时间复杂度是bb O(M.tu X N.tu/N.mu);bb压缩存储的时间复杂度是O(M.tu X N.tu/N.mu);O(M.tu X N.tu/N.m

25、u);bb时间复杂度是:bb O(M.mu X N.nu+M.tu X N.tu/N.mu);O(M.mu X N.nu+M.tu X N.tu/N.mu);bbfor(i=1;i=m1;+i)for(i=1;i=m1;+i)bb for(j=1;j=n2;+j)bb Qij=0;bb for(k=1;k=n1;+k)bb Qij+=Mik*Nkj;bb /算法复杂度是 O(m1*n1*n2)现在学习的是第25页，共26页实验与习题bb理论习题 5.6,5.7,5.8,5.9bb实验题:写一个主程序来写一个主程序来上机验证求稀疏矩阵求稀疏矩阵M M的转置矩阵的转置矩阵T T的快的快速方法速方法的存储结构；并计算的存储结构；并计算A A的转置的转置 15 0 0 22 A=0 -6 0 0 A=0 -6 0 0 91 0 0 0 5.21现在学习的是第26页，共26页