创意网站建设设计公司,学室内设计去哪里学比较好,wordpress注册页面地址,苏州专业设计网站稀疏矩阵#xff1a;
在矩阵中#xff0c;若数值为0的元素数目远远多于非0元素的数目#xff0c;并且非0元素分布没有规律时#xff0c;则称该矩阵为稀疏矩阵#xff1b;与之相反#xff0c;若非0元素数目占大多数时#xff0c;则称该矩阵为稠密矩阵。定义非零元素的总…稀疏矩阵
在矩阵中若数值为0的元素数目远远多于非0元素的数目并且非0元素分布没有规律时则称该矩阵为稀疏矩阵与之相反若非0元素数目占大多数时则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。 特性 1.稀疏矩阵其非零元素的个数远远小于零元素的个数而且这些非零元素的分布也没有规律。 2.稀疏因子是用于描述稀疏矩阵的非零元素的比例情况。设一个n*m的稀疏矩阵A中有t个非零元素则稀疏因子δδ的计算公式如下δtn∗mδtn∗m(当这个值小于等于0.05时可以认为是稀疏矩阵)
矩阵压缩
存储矩阵的一般方法是采用二维数组其优点是可以随机地访问每一个元素因而能够较容易地实现矩阵的各种运算如转置运算、加法运算、乘法运算等。 对于稀疏矩阵来说采用二维数组的存储方法既浪费大量的存储单元用来存放零元素又要在运算中花费大量的时间来进行零元素的无效计算。所以必须考虑对稀疏矩阵进行压缩存储。
最常用的稀疏矩阵存储格式主要有COOCoordinate Format和CSRCompressed Sparse Row。
COO很简单就是使用3个数组分别存储全部非零元的行下标row index、列下标column index和值valueCSR稍复杂对行下标进行了压缩假设矩阵行数是m则压缩后的数组长度为m1记作row ptr其中第i个元素0-base表示矩阵前i行的非零元个数。
1CoordinateCOO 这是最简单的一种格式每一个元素需要用一个三元组来表示分别是行号列号数值对应上图右边的一列。这种方式简单但是记录单信息多行列每个三元组自己可以定位因此空间不是最优。
2Compressed Sparse Row (CSR) CSR是比较标准的一种也需要三类数据来表达数值列号以及行偏移。CSR不是三元组而是整体的编码方式。数值和列号与COO一致表示一个元素以及其列号行偏移表示某一行的第一个元素在values里面的起始偏移位置。如上图中第一行元素1是0偏移第二行元素2是2偏移第三行元素5是4偏移第4行元素6是7偏移。在行偏移的最后补上矩阵总的元素个数本例中是9。
CSC是和CSR相对应的一种方式即按列压缩的意思。 以上图中矩阵为例 Values [1 5 7 2 6 8 3 9 4] Row Indices[0 2 0 1 3 1 2 2 3] Column Offsets[0 2 4 7 9]
其他的存储格式如CSC,DIA,ELL,HYB等参考博文 http://blog.csdn.net/gggg_ggg/article/details/47402459
稀疏矩阵的实现
/** describe: sparse matrix* date: 2018/02/28*/#include stdio.h
#include stdlib.h
#include string.h
#include time.h
#include SparseMatrix.h
#include common.h
#include MyTime.h//coo转化为csr矩阵
void coo_to_csr_sparse_matrix(COOSparseMatrix *cm, CSRSparseMatrix *sm)
{unsigned int i, j;unsigned int tot 0;int nz, nr;nz cm-NonZeroNum;nr cm-rowNum 1;// Init mem for CSR matrixsm-val (double *)malloc(nz * sizeof(double));sm-col (unsigned int *)malloc(nz * sizeof(unsigned int));sm-ptr (unsigned int *)malloc(nr * sizeof(unsigned int));memset(sm-ptr, 0, nr * sizeof(unsigned int));sm-NonZeroNum cm-NonZeroNum;sm-rowNum cm-rowNum;sm-colNum cm-colNum;sm-ptr[0] tot;for (i 0; i sm-rowNum; i){for (j 0; j cm-NonZeroNum; j){if (cm-row[j] i){sm-val[tot] cm-val[j];sm-col[tot] cm-col[j];tot;sm-ptr[i 1] tot;}}}}//创建coo矩阵
void create_coo_sparse_matrix(COOSparseMatrix *cm)
{int i,nz;int m, n;double t;FILE *fp;nz cm-NonZeroNum;printf(len:%d\n, nz);cm-val (double *)malloc(nz * sizeof(double));cm-row (unsigned int *)malloc(nz * sizeof(unsigned int));cm-col (unsigned int *)malloc(nz * sizeof(unsigned int));m n 0;t 0.0;fp fopen(FILE_PATH, r);if (fp NULL){printf(file does not exist);return;}for (i 0; i nz; i){fscanf(fp, %d %d %lf\n, m, n, t);//printf(row:%d, col:%d, val:%lf\n, m, n, t);cm-row[i] m;cm-col[i] n;cm-val[i] t;}fclose(fp);
}//删除矩阵
void free_csr_sparse_matrix(CSRSparseMatrix *coo)
{ if (coo-col ! NULL)free(coo-col);if (coo-ptr ! NULL)free(coo-ptr);if (coo-val ! NULL)free(coo-val);coo-col NULL;coo-ptr NULL;coo-val NULL;coo-colNum coo-rowNum coo-NonZeroNum 0;
}void free_coo_sparse_matrix(COOSparseMatrix *coo)
{if (coo-row ! NULL)free(coo-row);if (coo-col ! NULL)free(coo-col);if (coo-val ! NULL)free(coo-val);coo-row NULL;coo-col NULL;coo-val NULL;coo-colNum coo-rowNum coo-NonZeroNum 0;}//矩阵加法
int SparseMatrixAdd(CSRSparseMatrix sm1, CSRSparseMatrix sm2, CSRSparseMatrix *output)
{if (sm1.colNum ! sm2.colNum || sm1.rowNum ! sm2.rowNum)return ERR_FAILED;//to be definedreturn ERR_OK;
}//y mx
void csr_SPMV(CSRSparseMatrix *csr, double *x, double *y)
{unsigned int i, j, end;double sum;double *val csr-val;unsigned int *col csr-col;unsigned int *ptr csr-ptr;end 0;// Loop over rows.for (i 0; i csr-rowNum; i){sum 0.0;j end;end ptr[i 1];// Loop over non-zero elements in row i.for (; j end; j){sum val[j] * x[col[j]];}y[i] sum;}
}void display_csr_matrix(CSRSparseMatrix *sm)
{unsigned int i,j;printf(val );for (i 0; i sm-NonZeroNum; i){printf(%.2g | , sm-val[i]);}j 1;printf(\ncol );for (i 0; i sm-NonZeroNum; i){printf(%d | , sm-col[i]);}printf(\nptr );for(i0; i sm-rowNum 1; i){if (sm-ptr[i] ! 0 || i0)printf(%d | , sm-ptr[i]);}printf(\n);//printf(\tnz %d\n, m-nz);//printf(\trows %d\n, m-rows);//printf(\tcols %d\n, m-cols);
}void create_random_data(int len)
{ int m;int n;double a;int i;FILE *fp;fp fopen(FILE_PATH, w);if (fp NULL){printf(open file failed!\n);return;}printf(len is %d\n,len);srand((unsigned)time(NULL));for (i 0; i len; i){/*create random data*/m rand() % 100;n rand() % 100;a rand() / (double)(RAND_MAX);fprintf(fp, %d %d %lf\n, m, n, a);}fclose(fp);
}int main(int argc, char *argv[])
{ double *x;double *y;int m_rows 100;int m_cols 100;int n_zeros 9;int loops 1000;MyTime mytime;int i;COOSparseMatrix coo;CSRSparseMatrix csr;LINEPRINT;//create_random_data(n_zeros);if (strcmp(create, argv[1]) 0){printf(now create random data!\n);create_random_data(n_zeros); }coo.rowNum m_rows;coo.NonZeroNum n_zeros;coo.colNum m_cols;create_coo_sparse_matrix(coo);coo_to_csr_sparse_matrix(coo, csr);display_csr_matrix(csr);free_coo_sparse_matrix(coo);x (double *)malloc(m_cols *sizeof(double));y (double *)malloc(m_rows *sizeof(double));for (i 0; i csr.colNum; i){x[i] i 1;}//计算y mx的时间time_start(mytime);for (i 0; i loops; i){csr_SPMV(csr, x, y);}time_stop(mytime);printf(smmv use time:%lf\n, mytime.sec);free_csr_sparse_matrix(csr);free(x);free(y);x NULL;y NULL;exit(EXIT_SUCCESS);return 0;}主要实现了coo创建稀疏矩阵转化为csr稀疏矩阵以及稀疏矩阵的矢量乘法
结果
稀疏矩阵的优化
最近考虑稀疏矩阵的优化但是看不到MKL的实现想了几个思路不知道对稀疏矩阵的优化有没有帮助暂时先记下来。 1.多线程。使用openmp或者mpi 2.numanode awareness 特性。把稀疏矩阵的存储均匀地分配到两颗处理器各自的本地内存中最大程度的利用内存带宽 3.利用硬件cache特性对矩阵进行分块或矩阵的循环进行限制 4.利用pipeline多流水线并行处理 5.自适应分块存储结构。由于稀疏矩阵的非零元分布不一定均匀有的分块会非常稀疏有的则会相对稠密。对于极稀疏的分块非零元数量远小于行数如果用和CSR相似的压缩行存储策略则会浪费空间所以用COO的方式反而更能节省存储空间提高访问效率。
