实验指导书--稀疏矩阵存储与向量乘运算

上机实验一:稀疏矩阵存储与向量乘运算一、实验目的：学习稀疏矩阵存储的CompressedRowStorage技术与此基础上的矩阵向量乘方法，分析其（内存）空间与时间复杂度与直接存储方法之间的差别。二、基本知识：通过有限元方法离散的得到的矩阵都是稀疏矩阵，即其大部分矩阵元素都为0。因此在程序编写过程中采用二维的数组来存储非常浪费内存，因此需要采用一种有效的方法来保存稀疏矩阵。CompressedRowStorage(CRS)就是这样一种常用高效的稀疏存储技术。考虑一个一般的N×N矩阵MatA,如果以二维数组存储，其内存需求为：O(N2)矩阵向量乘运算量为：O(N2).对于一个稀疏N×N矩阵MatA，其非零元素个数为Ns,定义三个一维数组:­Val[Ns]按行-列方式依次存储矩阵中每个非零元素；­Col_ind[Ns]对应记录Val中每个元素所在的列数；­row_ptr[N+1]记录每一行第一个元素在Val中的位置。如此：•第i行非零元素的个数为：row_ptr[i+1]-row_ptr[i]•第i行的非零元素有：val[row_ptr[i]],...,val[row_ptr[i+1]-1]。【例】：012345012345C++CodeDemo//CompressedRowStorageformat//forasparsesquare(mSizeXmSize)matrixpublicclassCRS{//thevaluesofthenonzeroelementsofthematrixfloat[]val;//thecolumnindicesoftheelementsinvalarrayint[]col_idx;//locationsinthevalandcol_idxarraythatstartarowint[]row_ptr;//thesizeofthematrix:thenumberofrowsintmSize=0;//constructorthattakesasparsematrixandconvertittoaCRSobjectCRS(float[][]matrix){...}//printthematrixinCRSformat.publicvoidprintCRS(){...}//testtheprogrampublicstaticvoidmain(String[]args){...}}CRS(float[][]matrix){inti,j,index;//thetotalnumberofnonzerointhematrixinttotalNonZeros;//getthenumberofrowsandcolumnsmSize=matrix.length;//getthetotalnumberofnonzeroentriesinthematrixtotalNonZeros=0;for(i=0;imSize;i++){for(j=0;jmSize;j++){if(matrix[i][j]!=0)totalNonZeros++;}}//allocatememoryforvalandcol_idxarrayval=newfloat[totalNonZeros];col_idx=newint[totalNonZeros];//allocatememoryforrow_ptrrow_ptr=newint[mSize+1];row_ptr[0]=0;//storethematrixinCRSformatindex=0;//pointtothenextpositiontostorethevaluefor(i=0;imSize;i++){//eachrowfor(j=0;jmSize;j++){//eachcolumnif(matrix[i][j]!=0){//addthevaluetovalval[index]=matrix[i][j];//recordthecolumnindexincol_idxcol_idx[index]=j;index++;}}//updaterow_ptrrow_ptr[i+1]=index;}}//endofCRS(float[][]matrix)//testtheprogrampublicstaticvoidmain(String[]args){float[][]matrix={{10,0,0,0,-2,0},{3,9,0,0,0,3},{0,7,8,7,0,0},{3,0,8,7,5,0},{0,8,0,9,9,13},{0,4,0,0,2,-1}};System.out.println(theoriginalsparsematrix);for(inti=0;i6;i++){for(intj=0;j6;j++){System.out.print(matrix[i][j]+,);}System.out.println();}System.out.println();CRScrs=newCRS(matrix);crs.printMatrix();crs.printCRS();}三、实验任务（课上检验，不要求实验报告）：实验一:用Matlab实现一个10×10稀疏矩阵的CRS存储步骤一：生成一个随机的二维矩阵。步骤二：分别二维数组和采用CRS技术存储此矩阵；实验二：用Matlab实现一个随机1000×1000稀疏矩阵的CRS存储后，记录进行50次矩阵向量乘运算（第一次运算所用向量为随机生成/单位向量，之后的运算中向量为上次计算的结果向量），并与以二维数组方式存储此数组做同样操作的计算时间做比较。四、相关参考代码：N=1000;%sizeofmatrixdens=0.1;%densityofthesparsematrixma=sprand(N,N,dens);%generatearandomsparsematrixtic;%starttimerforii=1:N%storein2Darrayforjj=1:Nmat(ii,jj)=ma(ii,jj);endendv=rand(N,1);%generatearandvector%rhs=mat*v;toc%showrunningtimesincelasttic五、课后作业：1.分析CompressRowStorage（内存）空间复杂度和矩阵向量乘运算复杂度。2.对于有限元稀疏矩阵的存储，本次实验采用的CompressRowStorage方法可以进一步优化么？（第一个提出一种新型改进算法的同学，有奖励！）