csr 矩阵编码,CSR矩阵 - 矩阵乘法

﹏ヽ暗。殇╰゛Y 2022-08-30 11:14 199阅读 0赞

![Image 1][]

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\],

\# 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.

[Image 1]: