当前位置：首页 > news >正文

矩阵压缩格式转换：COO转换CSC（C++）

news 2024/10/30 13:11:12

一、基本理论

1.1 COO格式

1.2 CSR格式

1.3 CSC格式

二、代码实现

三、测试

一、基本理论

稀疏矩阵（Sparse Matrix）是大部分元素为零的矩阵，与之相对应的是稠密矩阵（Dense Matrix）。科学领域、工程计算、图形处理、机器学习等领域的大多数数据以稀疏矩阵的形式呈现。由于稀疏矩阵中含有大量的零元素，在矩阵计算过程中许多元素的迭代计算属于无效运算，为了减少不必要的运算，需要对稀疏矩阵进行处理，减少CPU和内存的无效消耗。最为有效、使用最广的方法是矩阵压缩，即稀疏矩阵存储时仅存储非0的数值以节约内存，计算时仅计算非0的部分以减少CPU消耗。

常见的稀疏矩阵存储格式有：COO、CSR、CSC。

以4x5的稀疏矩阵A为例：

$A=\begin{bmatrix} 1 & 4 & 0 & 0 & 0\\ 0& 2 & 3 & 0 & 0\\ 5& 0 & 0 & 7 & 8\\ 0& 0 & 9 & 0 & 6 \end{bmatrix}$

1.1 COO格式

COO格式最为简单，与二维直角坐标系中某个点g=f(x,y)的表示形式相似，由行索引矩阵、列索引矩阵、非零数值矩阵组成，矩阵A对应的COO格式为：

$COO\left\{\begin{matrix} data=[1\;\;4\;\;2\;\;3\;\;5\;\;7\;\;8\;\;9\;\;6]\\ row=[0\;\;0\;\;1\;\;1\;\;2\;\;2\;\;2\;\;3\;\;3]\\ col=[0\;\;1\;\;1\;\;2\;\;0\;\;3\;\;4\;\;2\;\;4] \end{matrix}\right.$

1.2 CSR格式

CSR（Compressed Sparse Row）格式由行指针矩阵、列索引矩阵、非零数值矩阵组成，矩阵A对应的CSR格式为：

$CSR\left\{\begin{matrix} data=[1\;\;4\;\;2\;\;3\;\;5\;\;7\;\;8\;\;9\;\;6]\\ ptr=[0\;\;2\;\;4\;\;7\;\;9]\\ col=[0\;\;1\;\;1\;\;2\;\;0\;\;3\;\;4\;\;2\;\;4] \end{matrix}\right.$

具体含义：非零数值矩阵和COO格式中的一致。假设有m行，行指针矩阵有m+1个元素，行指针矩阵中前m个元素为每一行的第一个非零数在数据矩阵中的角标，

第一行的第一个非零元素为1，在数据矩阵中为第0个元素；

第二行的第一个非零元素为2，在数据矩阵中为第2个元素；

第三行的第一个非零元素为5，在数据矩阵中为第4个元素；

第四行的第一个非零元素为9，在数据矩阵中为第7个元素。

在行指针矩阵中，最后一个元素的值统一为整个矩阵中非零元素的总值，即为m。

1.3 CSC格式

CSC（Compressed Sparse Column）格式与CSR格式类似，只是CSC是列压缩，CSR为行压缩，由行索引矩阵、列指针矩阵、非零数值矩阵组成，矩阵A对应的CSC格式为：

$CSC\left\{\begin{matrix} data=[1\;\;5\;\;4\;\;2\;\;3\;\;9\;\;7\;\;8\;\;6]\\row=[0\;\;2\;\;0\;\;1\;\;1\;\;3\;\;2\;\;2\;\;3] \\ ptr=[0\;\;2\;\;4\;\;6\;\;7\;\;9]\end{matrix}\right.$

具体含义：非零数值矩阵和COO格式中的一致。假设有n列，列指针矩阵有n+1个元素，列指针矩阵中前n个元素为每一列的第一个非零数在数据矩阵中的角标，

第一列的第一个非零元素为1，在数据矩阵中为第0个元素；

第二列的第一个非零元素为4，在数据矩阵中为第2个元素；

第三列的第一个非零元素为3，在数据矩阵中为第4个元素；

第四列的第一个非零元素为7，在数据矩阵中为第6个元素；

第五列的第一个非零元素为8，在数据矩阵中为第7个元素。

在行指针矩阵中，最后一个元素的值统一为整个矩阵中非零元素的总值，即为n。

二、代码实现

#include <stdlib.h>
#include <stdio.h>#pragma warning(disable:4996)int main(int argc, char *argv[])
{FILE *fp_a;FILE *fp_b;const char *filename1, *filename2, *filename3, *filename4;int i;int row_num, col_num, data_num, b_row_num, b_col_num;int *row, *col, *row1, *col1;double *data, *data1, *b;double e;//1//从原始稀疏矩阵数据文件中读取数据fp_b = fopen("Y_out_coo.txt", "r");if(fp_b == NULL){printf("Cannot open file a.\n");exit(0);}//从原始稀疏矩阵数据文件中读取矩阵的行数，列数，非零数目fscanf(fp_b, "%d %d %d", &row_num, &col_num, &data_num);printf("%d %d %d\n\n", row_num, col_num, data_num);//为读取矩阵市场的系数矩阵的行数组（row），列数组（col），数据数组开辟空间（data）row = (int*)malloc(sizeof(int)*data_num);col = (int*)malloc(sizeof(int)*data_num);data = (double*)malloc(sizeof(double)*data_num);//为稀疏矩阵csr格式的行数组（row1），列数组（col1），数据数组开辟空间（data1）row1 = (int*)malloc(sizeof(int)*data_num);col1 = (int*)malloc(sizeof(int)*(col_num+1));data1 = (double*)malloc(sizeof(double)*data_num);//从原始稀疏矩阵数据文件中读取矩阵全部的行元素，列元素，非零元数据//原始稀疏矩阵数据文件中存储的非零元素的行坐标，列坐标均从1开始for(i = 0; i < data_num; i++){fscanf(fp_b, "%d %d %lf", &row[i], &col[i], &data[i]);printf("%d %d %lf\n", row[i], col[i], data[i]);}fclose(fp_b);printf("稀疏矩阵coo格式读入完毕！\n");//输入Ax=b中b数据//从原始稀疏矩阵数据文件中读取数据fp_b = fopen("b_out_coo.txt", "r");if(fp_b == NULL){printf("Cannot open file b_out_coo\n");exit(0);}//从原始稀疏矩阵数据文件中读取矩阵的行数，列数，非零元数目fscanf(fp_b, "%d %d", &b_row_num, &b_col_num);printf("%d %d\n", b_row_num, b_col_num);//创建b数组输入b = (double*)malloc(sizeof(double)*b_row_num);for(i = 0; i < b_row_num; i++){fscanf(fp_b, "lf", &b[i]);}fclose(fp_b);printf("Ab数据读入完毕！\n");//2//矩阵coo格式转化为csc格式int j, k, count;count = 0;k = 0;for(i = 0; i <= col_num; i++)  //初始化csc格式的列数组{col1[i] = 0;}for(i = 0; i < data_num; i++)  //记录每列的数据数目{col1[col[i]]++;}for(i = 1; i <= col_num; i++)  //计算csc格式的列信息的数组，这里命名为row1{i = col1[col[j]-1]++;row1[i] = row[j] - 1;data1[i] = data[j];printf("%lf\n", data[j]);}printf("First step: csc col info has been done! \n");/**********输出文件名***********/filename1 = "Y_out_CSC_Ap.txt";filename2 = "Y_out_CSC_Ai.txt";filename3 = "Y_out_CSC_Ax.txt";filename4 = "Y_out_CSC_Ab.txt";if((fp_b = fopen(filename1, "w")) == NULL){printf("Cannot open file write!\n");exit(0);}for(i = 0; i < col_num; i++){fprintf(fp_b, "%d", col1[i]);fprintf(fp_b, ", ");}fclose(fp_b);if((fp_b = fopen(filename2, "w")) == NULL){fprintf(fp_b, "%d", row1[i]);fprintf(fp_b, ", ");}fclose(fp_b);if((fp_b = fopen(filename3, "w")) == NULL){printf("Cannot open file write\n");exit(0);}for(i = 0; i < data_num; i++){fprintf(fp_b, "%lf", data1[i]);fprintf(fp_b, ", ");}fclose(fp_b);if((fp_b = fopen(filename4, "w")) == NULL){printf("Cannot open file write\n");exit(0);}for(i = 0; i < b_row_num; i++){fprintf(fp_b, "%.10lf", b[i]);fprintf(fp_b, ", ");}fclose(fp_b);printf("Coo has been transformed to CSC!\n");//释放申请的数组空间free(row);free(col);free(data);free(row1);free(col1);free(data1);free(b);return 0;
}