CSR Matrix - Matrix moltiplicazione

Question

Ho due matrici quadrate A e B

devo convertire B-CSR Format e determinare il prodotto C

A * B_csr = C 

ho trovato un sacco di informazioni on-line per quanto riguarda CSR Matrix - Vector multiplication. L'algoritmo è:

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

Tuttavia, ho bisogno Matrix - Matrix moltiplicazione.

Inoltre, sembra che la maggior parte degli algoritmi applichi la moltiplicazione A_csr - vector in cui è necessario A * B_csr. La mia soluzione è di trasporre le due matrici prima di convertire e quindi trasporre il prodotto finale.

Qualcuno può spiegare come calcolare un prodotto Matrix - CSR Matrix e/o un prodotto CSR Matrix - Matrix?

Answer 1

Ecco una semplice soluzione in Python per Dense Matrix X CSR Matrix. Dovrebbe essere auto-esplicativo.

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 è in realtà solo una sequenza di CSR Matrix X Vector prodotto per ogni riga della matrice densa giusto? Quindi dovrebbe essere davvero facile estendere il codice che mostri sopra per farlo.

Andando avanti, suggerisco di non codificare queste routine da soli. Se stai usando C++ (basato sul tag), potresti dare un'occhiata a Boost ublas per esempio o Eigen. Le API possono sembrare un po 'criptiche all'inizio, ma ne vale davvero la pena a lungo termine. Innanzitutto, hai accesso a molte più funzionalità, che probabilmente richiedi in futuro. In secondo luogo queste implementazioni saranno meglio ottimizzate.