csr 矩陣 編碼_CSR矩陣 - 矩陣乘法

I have two square matrices A and B

I must convert B to CSR Format and determine the product C

A * B_csr = C

I have found a lot of information online regarding CSR Matrix - Vector multiplication. The algorithm is:

for (k = 0; k < N; k = k + 1)

result[i] = 0;

for (i = 0; i < N; i = i + 1)

{

for (k = RowPtr[i]; k < RowPtr[i+1]; k = k + 1)

{

result[i] = result[i] + Val[k]*d[Col[k]];

}

}

However, I require Matrix - Matrix multiplication.

Further, it seems that most algorithms apply A_csr - vector multiplication where I require A * B_csr. My solution is to transpose the two matrices before converting then transpose the final product.

Can someone explain how to compute a Matrix - CSR Matrix product and/or a CSR Matrix - Matrix product?

解決方案

Here is a simple solution in Python for the Dense Matrix X CSR Matrix. It should be self-explanatory.

def main():

# 4 x 4 csr matrix

# [1, 0, 0, 0],

# [2, 0, 3, 0],

# [0, 0, 0, 0],

# [0, 4, 0, 0],

csr_values = [1, 2, 3, 4]

col_idx = [0, 0, 2, 1]

row_ptr = [0, 1, 3, 3, 4]

csr_matrix = [

csr_values,

col_idx,

row_ptr

]

dense_matrix = [

[1, 3, 3, 4],

[1, 2, 3, 4],

[1, 4, 3, 4],

[1, 2, 3, 5],

]

res = [

[0, 0, 0, 0],

[0, 0, 0, 0],

[0, 0, 0, 0],

[0, 0, 0, 0],

]

# matrix order, assumes both matrices are square

n = len(dense_matrix)

# res = dense X csr

csr_row = 0 # Current row in CSR matrix

for i in range(n):

start, end = row_ptr[i], row_ptr[i + 1]

for j in range(start, end):

col, csr_value = col_idx[j], csr_values[j]

for k in range(n):

dense_value = dense_matrix[k][csr_row]

res[k][col] += csr_value * dense_value

csr_row += 1

print res

if __name__ == '__main__':

main()

CSR Matrix X Dense Matrix is really just a sequence of CSR Matrix X Vector product for each row of the dense matrix right? So it should be really easy to extend the code you show above to do this.

Moving forward, I suggest you don't code these routines yourself. If you are using C++ (based on the tag), then you could have a look at Boost ublas for example, or Eigen. The APIs may seem a bit cryptic at first but it's really worth it in the long term. First, you gain access to a lot more functionality, which you will probably require in the future. Second these implementations will be better optimised.