c-将crs格式的稀疏矩阵自身相乘，得到乘积

Question

我试图通过使用经典的naive方法与使用压缩行存储来比较NxN矩阵乘法的加速。矩阵中的值是二进制的，要么是0，要么是1。

在经典的矩阵乘法中，矩阵本身的乘法是直接的，如下所示：

for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
for (k = 0; k < N; k++) {
product[i][j] += mat[i][k]*mat[k][j];
}

}
}

在压缩行存储格式中，我需要将矩阵存储在一个数组col_idx中，该数组存储非零值的所有列索引。我还需要一个行指针，它将索引编码在给定行开始的col_idx中。

例如，如果我们将以下矩阵本身相乘，我们就得到了乘积：

矩阵多重

给定矩阵中的列索引和行指针将具有数组值：

col_idx = [1,2,2,3,0,3,1]
row_ptr = [0,2,4,6,7]

要获得一行的列索引，比如说第一行，我只需要输入以下代码：

for (i = row_ptr[0]; i < row_ptr[1]; i++) {
printf("%dn",col_idx[i]);
}

我想得到与CRS算法的经典矩阵乘法相同的乘积，但在只存储非零值的1D阵列中，在本例中为：

product1D = [1,1,2,1,1,2,2,1,1,1]

我试着在同一时间得到所有的排，但我被我应该做的事情卡住了。有什么建议吗？

Answer 1

中的实现https://www.geeksforgeeks.org/operations-sparse-matrices/(C++(很好：

void multiply(sparse_matrix b) 
{ 
if (col != b.row) 
{ 
// Invalid multiplication 
cout << "Can't multiply, Invalid dimensions"; 
return; 
} 
// transpose b to compare row 
// and col values and to add them at the end 
b = b.transpose(); 
int apos, bpos; 
// result matrix of dimension row X b.col 
// however b has been transposed, 
// hence row X b.row 
sparse_matrix result(row, b.row); 
// iterate over all elements of A 
for (apos = 0; apos < len;) 
{ 
// current row of result matrix 
int r = data[apos][0]; 
// iterate over all elements of B 
for (bpos = 0; bpos < b.len;) 
{ 
// current column of result matrix 
// data[,0] used as b is transposed 
int c = b.data[bpos][0]; 
// temporary pointers created to add all 
// multiplied values to obtain current 
// element of result matrix 
int tempa = apos; 
int tempb = bpos; 
int sum = 0; 
// iterate over all elements with 
// same row and col value 
// to calculate result[r] 
while (tempa < len && data[tempa][0] == r && 
tempb < b.len && b.data[tempb][0] == c) 
{ 
if (data[tempa][1] < b.data[tempb][1]) 
// skip a 
tempa++; 
else if (data[tempa][1] > b.data[tempb][1]) 
// skip b 
tempb++; 
else
// same col, so multiply and increment 
sum += data[tempa++][2] *  
b.data[tempb++][2]; 
} 
// insert sum obtained in result[r] 
// if its not equal to 0 
if (sum != 0) 
result.insert(r, c, sum); 
while (bpos < b.len &&  
b.data[bpos][0] == c) 
// jump to next column 
bpos++; 
} 
while (apos < len && data[apos][0] == r) 
// jump to next row 
apos++; 
} 
result.print(); 
} 

稀疏矩阵的C++构造函数是这样定义的

sparse_matrix(int r, int c) 
{ 
// initialize row 
row = r; 
// initialize col 
col = c; 
// initialize length to 0 
len = 0; 
//Array of Pointer to make a matrix 
data = new int *[MAX]; 
// Array representation 
// of sparse matrix 
//[,0] represents row 
//[,1] represents col 
//[,2] represents value 
for (int i = 0; i < MAX; i++) 
data[i] = new int[3]; 
} 

带int** data

在中https://codingee.com/c-programs/c-program-for-multiplication-of-two-sparse-matrices/是C代码