CSR Matrix - Matrixmultiplikation

Question

Ich habe zwei quadratische Matrizen A und B

I B-CSR Format und bestimmen das Produkt C

A * B_csr = C 

Ich habe eine Menge Informationen online zu finden in Bezug auf CSR Matrix - Vector multiplication konvertieren. Der Algorithmus ist:

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]]; 
    } 
} 

Allerdings benötige ich Matrix - Matrix Multiplikation.

Weiterhin scheint es, dass die meisten Algorithmen A_csr - vector Multiplikation anwenden, wo ich A * B_csr benötige. Meine Lösung besteht darin, die beiden Matrizen vor der Umwandlung zu transponieren und dann das Endprodukt zu transponieren.

Kann jemand erklären, wie man ein Matrix - CSR Matrix Produkt und/oder ein CSR Matrix - Matrix Produkt berechnet?

Answer 1

Hier ist eine einfache Lösung in Python für die Dense Matrix X CSR Matrix. Es sollte selbsterklärend sein.

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 ist wirklich nur eine Folge von CSR Matrix X Vector Produkt für jede Zeile der dichten Matrix richtig? Daher sollte es sehr einfach sein, den obigen Code zu erweitern.

Vorwärts, ich schlage vor, dass Sie diese Routinen nicht selbst programmieren. Wenn Sie C++ (basierend auf dem Tag) verwenden, können Sie sich beispielsweise Boost ublas oder Eigen ansehen. Die APIs mögen auf den ersten Blick etwas kryptisch erscheinen, aber auf lange Sicht ist es das wirklich wert. Erstens erhalten Sie Zugang zu einer Menge weiterer Funktionen, die Sie wahrscheinlich in Zukunft benötigen werden. Zweitens werden diese Implementierungen besser optimiert.